3784497989

18 Adam Osękowski i Łukasz Rajkowski

Zadanie 6. W pewnym turnieju uczestniczyło n zawodników. Każdy z nich rozegrał jedną partię z każdym innym zawodnikiem, nie było remisów. Udowodnić, że albo można podzielić uczestników turnieju na takie dwie grupy A i B, że każdy zawodnik z grupy A wygrał z każdym z grupy B, albo można ustawić uczestników w ciąg U\, «2, ■■■, u_n tak, że Ui wygrał z «2, ^u2 wygrał z W3, ..., u_n_i wygrał z u_n, u_n wygrał z u\.

Rozwiązanie

Dowolny ciąg zawodników tą, tą, ..Vk taki, że v\ wygrał z tą, tą wygrał z tą,... ,Vk-i wygrał zą, Vk wygrał z tą (k ^2), będziemy nazywać cyklem.

Rozważymy dwa przypadki:

1.    Nie istnieje ani jeden cykl. Weźmy pod uwagę zawodnika u, który wygrał najwięcej partii (jeśli jest kilku takich zawodników, wybieramy dowolnego z nich). Rozumując jak w zadaniu 2, jeśli istnieje zawodnik v, który wygrał z u, to istnieje taki zawodnik w, który przegrał z u oraz wygrał z v, co stanowi sprzeczność z założeniem rozważanego przypadku. Oznacza to, iż zawodnik u wygrał ze wszystkimi; jako zbiór A bierzemy więc {w}, a jako B zbiór wszystkich pozostałych zawodników.

2.    Istnieje co najmniej jeden cykl. Niech m będzie największą liczbą naturalną taką, że istnieje cykl długości m. Jeżeli m = n, to teza zadania jest prawdziwa (istotnie — zachodzi jedna z postulowanych możliwości). Przypuśćmy zatem, że m<n i oznaczmy cykl długości m jako

V\ —> tą —> tą —i► • • • —iy v_m —i> V\.

Niech w będzie dowolnym zawodnikiem różnym od tą,tą,...,t;_m. Udowodnimy, że wszyscy zawodnicy cyklu uzyskali w meczu z zawodnikiem w ten sam rezultat (wszyscy wygrali albo wszyscy przegrali). Gdyby tak nie było, to moglibyśmy wskazać dwóch kolejnych zawodników Vi, Vi+1 (przyjmujemy v_m+i = tą), z których pierwszy wygrał z zawodnikiem w, a drugi przegrał. Umieszczając między tą a tą+1 zawodnika w stworzylibyśmy nowy, dłuższy cykl, co przeczyłoby maksymalności liczby m.

Tak więc każdy zawodnik spoza maksymalnego cyklu albo wygrał, albo przegrał wszystkie mecze z zawodnikami należącymi do tego cyklu. Możemy podzielić wszystkich zawodników różnych od tą,tą,... ,t;_m na dwa podzbiory: C, złożony z zawodników, którzy wygrali ze wszystkimi V!,v₂,... ,n_m, oraz D, składający się z zawodników, którzy przegrali partie z v 1, v2, • • •, v_m. Oczywiście, może się zdarzyć, że jeden ze zbiorów C, D jest pusty; nie mogą być jednak oba puste, gdyż założyliśmy, że m <n. Jeśli C jest pusty, bierzemy

A=    B = D,