XLI OM - III - Zadanie 3

Zawody matematyczne:

XLI OM, 1989-1990

Etap:

III

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. Dowieść, ż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_1, u_2, \ldots , u_n$ tak, że $u_1$ wygrał z $u_2$ , $u_2$ wygrał z $u_3$ , ..., $u_{n-1}$ wygrał z $u_n$ , $u_n$ wygrał z $u_1$ .

Rozwiązanie

Stwierdzenie, że zawodnik $x$ był zwycięzcą w spotkaniu z $y$ , będziemy notować za pomocą strzałki: $x \to y$ .

Dowolny ciąg $k$ zawodników $u_1, u_2,\ldots,u_k$ ( $k \geq 3$ ) taki, że

$ u_1 \to u_2 \to u_3 \to \ldots \to u_{k-1} \to u_k \to u_1 $

będziemy nazywać cyklem długości $k$ .

Jeśli $A$ , $B$ są rozłącznymi niepustymi podzbiorami zbioru zawodników, mającymi tę własność, że każdy zawodnik ze zbioru $A$ pokonał każdego zawodnika ze zbioru $B$ , będziemy mówić, że grupa $A$ zdominowała grupę $B$ .

Należy wykazać, że albo zbiór wszystkich zawodników można podzielić na dwa niepuste podzbiory, z których jeden dominuje drugi, albo istnieje cykl długości $n$ .

Rozpatrzymy dwa przypadki.

Przypadek I. Nie istnieje ani jeden cykl.

Weźmy pod uwagą zawodnika $w$ , który wygrał najwięcej partii. Jeśli maksymalna liczba zwycięstw jest udziałem kilku zawodników, wybieramy któregokolwiek z nich (i jego oznaczamy literą $w$ ); zresztą okaże się za chwilę, że taka sytuacja nie jest możliwa - udowodnimy bowiem, że $w$ wygrał wszystkie partie.

Przypuśćmy, że tak nie jest i niech $U$ będzie zbiorem tych zawodników, z którymi $w$ wygrał, zaś $V$ - zbiorem tych zawodników, z którymi $w$ przegrał. W myśl uczynionego przypuszczenia, zbiór $V$ nie jest pusty. Wybierzmy dowolnego zawodnika $v$ ze zbioru $V$ . Gdyby się okazało, że $v$ pokonał wszystkich zawodników ze zbioru $U$ , znaczyłoby to, że $v$ ma na swym koncie więcej zwycięstw niż $w$ , co nie jest możliwe. Musi więc istnieć w zbiorze $U$ zawodnik $u$ , który wygrał z $v$ . Trójka zawodników $u$ , $v$ , $w$ tworzy cykl: $u \to v \to w \to u$ , wbrew założeniu o nieistnieniu cykli. Otrzymana sprzeczność dowodzi niesłuszności przypuszczenia otwierającego ten akapit.

Wykazaliśmy w ten sposób, że zawodnik w pokonał wszystkich innych. Wystarczy teraz określić grupę $A$ jako zbiór jednoelementowy, zaliczając doń zawodnika $w$ ; wszyscy pozostali zawodnicy utworzą grupę $B$ , która jest zdominowana przez $A$ . Twierdzenie jest więc udowodnione w tym przypadku.

(Zauważmy, że wskazana metoda podziału nie jest jedyna; na przykład, można by było określić $B$ jako zbiór jednoelementowy, zaliczając doń tego zawodnika, który poniósł najwięcej porażek, a pozostałych zawodników umieszczając w grupie $A$ ; dowód poprawności i skuteczności takiego podziału byłby w pełni analogiczny. Zachęcamy Czytelników do znalezienia jeszcze innych metod dobrego podziału.)

Przypadek II. 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$ , znaczy to, że wszystkich zawodników można ustawić w cykl, więc zachodzi teza zadania.

W dalszym ciągu przyjmijmy, że $m < n$ . Niech

$ w_1 \to w_2 \to \ldots \to w_{m-1} \to w_m \to w_1 $

będzie cyklem długości $m$ i niech $z$ będzie dowolnym zawodnikiem różnym od $w_1$ , $w_2$ , \ldots, $w_m$ . Wykażemy, że wszyscy zawodnicy $w_i$ uzyskali w meczu z zawodnikiem $z$ identyczny rezultat (wszyscy wygrali albo wszyscy przegrali).

Przypuśćmy, że jest inaczej. Można wówczas wskazać dwóch kolejnych (w sensie cyklicznej numeracji) zawodników $w_j$ , $w_{j+1}$ , z których pierwszy wygrał z zawodnikiem $z$ , a drugi przegrał. Umieszczając $z$ między $w_j$ a $w_{j+1}$ tworzymy nowy cykl

$ w_1 \to \ldots \to w_j \to z \to w_{j+1} \to w_m \to w_1, $

długości $m+1$ . Jest to sprzeczność z maksymalnością liczby $m$ jako długości.

Zatem istotnie każdy zawodnik spoza maksymalnego cyklu albo wygrał albo przegrał wszystkie mecze z zawodnikami należącymi do tego cyklu. Możemy w takim razie podzielić wszystkich zawodników różnych od $w_1, \ldots, w_m$ na dwa podzbiory $U$ , $V$ , zaliczając do $U$ tych, którzy przegrali spotkania z wszystkimi $w_i$ , a do $V$ - tych, którzy wszystkie spotkania z zawodnikami $w_i$ wygrali. Może się zdarzyć, że jeden ze zbiorów $U$ , $V$ będzie pusty - nie mogą jednak oba być puste; wynika to z założenia, że $m < n$ .

Jeśli zbiór $U$ jest pusty, to przyjmując

$ A = V, \quad B = \{w_1,\ldots,w_m\} $

mamy podział zbioru wszystkich zawodników na grupy $A$ , $B$ takie, że $A$ dominuje $B$ . Jeżeli zbiór $V$ jest pusty, żądany podział uzyskamy biorąc

$ A = \{w_1,\ldots,w_m\}, \quad B = U. $

Przyjmijmy więc, że zbiory $U$ , $V$ są oba niepuste. Niech $u$ będzie dowolnym zawodnikiem ze zbioru $U$ , a $v$ - dowolnym zawodnikiem ze zbioru $V$ . Przypuśćmy, że $u$ wygrał z $v$ . W myśl określenia zbiorów $U$ i $V$ , zawodnik $u$ przegrał, a zawodnik $v$ wygrał mecze z wszystkimi $w_i$ ; w szczególności $u$ przegrał z $w_m$ , natomiast $v$ wygrał z $w_1$ . Mamy wobec tego cykl

$ u \to v \to w_1 \to w_2 \to \ldots \to w_{m-1} \to w_m \to u, $

długości $m+2$ ; sprzeczność z maksymalnością $m$ . Zatem zawodnik $u$ nie mógł wygrać z $v$ .

Ponieważ zawodników $u \in U$ , $v \in V$ wybraliśmy dowolnie, dochodzimy do wniosku, że wszyscy zawodnicy ze zbioru $U$ przegrali z wszystkimi zawodnikami ze zbioru $V$ ; zbiór $U$ jest zdominowany przez $V$ .