3784497986
Ekstremalny element, czyli o tym, co naj.. .
Adam Osękowski i Łukasz Rajkowski
Celem niniejszego artykułu jest zaprezentowanie pewnego podejścia do zadań kombinatorycznych. Z grubsza, metoda polega na wyróżnieniu ekstremalnego elementu i wykorzystaniu jego własności. Zilustrujemy to na kilku przykładach.
Zadanie 1. W pewnej grupie 30 osób każda zna co najmniej 25 osób spośród pozostałych. Udowodnić, że można wybrać spośród nich takie sześć osób, z których każde dwie się znają.
Rozwiązanie
Niech m będzie największą liczbą o tej własności, że można wybrać osoby Ai, A2, ..., Am, z których każde dwie się znają. Oznaczmy odpowiednio przez N\,N2, ■ • •, Nm zbiory nieznajomych dla A\, A2,.. - ,Am. Zgodnie z warunkami zadania, każda z osób A{ nie zna co najwyżej 4 osób, co pociąga za sobą, iż zbiór Ni U N2 U... U Nm ma co najwyżej 4m elementów. Z drugiej strony, zbiór ten musi mieć co najmniej 30 — m elementów: w przeciwnym razie spośród niewybranych 30—m osób moglibyśmy wybrać osobę znaną przez wszystkie osoby Ai, A2, ..., Am, co przeczyłoby maksymalności m. Otrzymaliśmy zatem 4m ^ 30 — m, czyli m ^ 6. Jest to równoważne tezie zadania.
Uwaga: Warto tu zauważyć, że liczby 6 nie można zwiększyć. Istotnie, rozważmy następujący przykład: oznaczmy osoby przez Ai, A2,..., żł.30 i przyjmijmy, że Ai zna Aj wtedy i tylko wtedy, gdy i, j dają różne reszty z dzielenia przez 6. Dla każdej liczby i, w zbiorze {1,2,..., 30} jest dokładnie pięć liczb o takiej samej reszcie z dzielenia przez 6 jak i, a zatem każda osoba nie zna dokładnie czterech spośród pozostałych i założenia zadania są spełnione. Nie można jednak wybrać siedmiu osób, z których każde dwie się znają: wśród dowolnych siedmiu liczb istnieją dwie, które dają tę samą resztę z dzielenia przez 6.
Zadanie 2. W turnieju tenisa stołowego wzięło udział n zawodników (n > 4).
Każdy zawodnik rozegrał dokładnie jeden mecz z każdym innym zawodnikiem, żaden mecz nie zakończył się remisem. Po turnieju wszyscy zawodnicy usiedli przy okrągłym stole w taki sposób, że każdy zawodnik wygrał z osobą siedzącą obok niego z jego lewej strony. Wykazać, że istnieją tacy trzej zawodnicy A, B, C, że A wygrał z B, B wygrał z C, zaś C wygrał z A.
Rozwiązanie
Wybierzmy zawodnika, który wygrał największą liczbę meczów i nazwijmy go A (jeśli jest kilku takich zawodników, wybieramy dowolnego spośród nich). Pozostałych n — 1 zawodników możemy podzielić na dwa zbiory: P — tych,
Wyszukiwarka
Podobne podstrony:
Ekstremalny element, czyli o tym, co naj... 17 skujemy, iż zarówno B, jak i B2 mają co najmniej n zn
Ekstremalny element, czyli o tym, co naj... 19 jeżeli zaś zbiór D jest pusty, kładziemy A = C, B = {
16 Adam Osękowski i Łukasz Rajkowski którzy przegrali z A oraz W — tych, którzy wygrali z A. Zauważm
18 Adam Osękowski i Łukasz Rajkowski Zadanie 6. W pewnym turnieju uczestniczyło n zawodników. Każdy
File0021 Według W. Pietrasa rządzenie składają się z cztery elementy: 1) decydowan
Papierowe rytmy w edukacji dzieci, czyli o tym w co lubi bawić się mózgmgr Dorota Dziamska REFERATPr
CCF20090831 029 34 Przedmowa
Rzecz nie w tym, co mówisz Ty - lecz w tym, co słyszą inni...... czyli jak uniknqć błędów przygotowu
IMGE76 Izabella Lignowska 258 I Mów
Technik Mechatronik Już dzisiaj pomyśl o tym, co chcesz robić w przyszłości, Czyli czym zajmuje
koresponduje z tym, co zostało już powiedziane o hermeneutycznym doświadczeniu Innego oraz elemencie
Co tak naprawdę jest w słoiczku? Czyli o tym, jak czytać składy kosmetyków.
Strona0268 268 W tym, co powiedziano, zawarty już jest cały szereg elementów klasyfikacji samowzbudn
dowolnym trzecim jego elementem ,to zachodzi ona też między owym pierwszym, a tym trzecim jego eleme
ciągła konfrontacja tego, co obserwujemy z tym, co na ten temat myślimy. Jej nieodłącznym elementem
więcej podobnych podstron