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, ..., A_m, z których każde dwie się znają. Oznaczmy odpowiednio przez N\,N2, ■ • •, N_m zbiory nieznajomych dla A\, A2,.. - ,A_m. 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 N_m 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, ..., A_m, 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,