3784497987

16 Adam Osękowski i Łukasz Rajkowski

którzy przegrali z A oraz W — tych, którzy wygrali z A. Zauważmy, iż każdy ze zbiorów P, W jest niepusty, na mocy warunków zadania. Rozważmy teraz dowolnego zawodnika C ze zbioru W. Gdyby C wygrał ze wszystkimi ze zbioru P, to — zważywszy, że wygrał także z A — miałby on więcej zwycięstw niż A, co przeczy wyborowi A. Zatem istnieje zawodnik B ze zbioru P, który wygrał z C. Trójka A, B, C posiada żądane własności.

Uwaga: Można także podać analogiczne rozwiązanie, w którym jako A bierzemy zawodnika, który przegrał największą liczbę meczów.

Zadanie 3. Na turnieju rycerskim każdy uczestnik posiada wśród pozostałych co najwyżej trzech śmiertelnych wrogów. Udowodnić, że można podzielić uczestników turnieju na dwie grupy tak, by dowolny uczestnik posiadał w swojej grupie co najwyżej jednego śmiertelnego wroga.

Uwaga: Jeżeli rycerz A jest śmiertelnym wrogiem rycerza B, to rycerz B jest śmiertelnym wrogiem rycerza A.

Rozwiązanie

Dla każdego podziału rycerzy na grupy rozpatrzmy liczbę konfliktów, tzn. liczbę par śmiertelnych wrogów, którzy znaleźli się w tej samej grupie. Rozważmy teraz podział na grupy, który stwarza najmniejszą możliwą liczbę konfliktów. Udowodnimy, że spełnia on żądane warunki. Przypuśćmy, że przy tym podziale znalazł się uczestnik, mający więcej niż jednego wroga w swojej grupie. Wówczas na mocy treści zadania posiada on co najwyżej jednego wroga w grupie przeciwnej. Przenosząc go do tej grupy, zmniejszymy liczbę konfliktów. Jest to sprzeczne z założeniem, że wybrany z początku podział stwarza najmniejszą możliwą ich liczbę.

Zadanie 4. W konferencji bierze udział 2n osób. Każdy uczestnik konferencji ma wśród pozostałych uczestników co najmniej n znajomych. Udowodnić, że wszystkich uczestników konferencji można zakwaterować w pokojach dwuosobowych tak, by każdy uczestnik mieszkał ze swoim znajomym.

Rozwiązanie

Niech m będzie maksymalną liczbą rozłącznych par znajomych wybranych spośród uczestników konferencji.

Oznaczmy uczestników przez A\, A2,..., Aim, B\, B2,.. ■, R2n-2m w taki sposób, że dla k osoby A2k-1 oraz A2k się znają; możemy to zapisać w sugestywnej postaci:

(Al, A2), (A3, A4), (A5, A>), ..., (Am-l, A2m), Bi, B2, ..., B2n-2m-

Załóżmy teraz, że m < n i weźmy pod uwagę uczestników B\ i i?2- Osoby te nie znają się, gdyż przeczyłoby to maksymalności liczby m. Analogicznie, żadna z tych osób nie zna nikogo spośród R3, R4, ...,B2_n-2m, skąd wnio-