Komentarz

XLI OM - III - Zadanie 3

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

\[<br /> u_1 \to u_2 \to u_3 \to \ldots \to u_{k-1} \to u_k \to u_1<br /> \]

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

\[<br /> w_1 \to w_2 \to \ldots \to w_{m-1} \to w_m \to w_1<br /> \]

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

\[<br /> w_1 \to \ldots \to w_j \to z \to w_{j+1} \to w_m \to w_1,<br /> \]

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

\[<br /> A = V, \quad B = \{w_1,\ldots,w_m\}<br /> \]

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

\[<br /> A = \{w_1,\ldots,w_m\}, \quad B = U.<br /> \]

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

\[<br /> u \to v \to w_1 \to w_2 \to \ldots \to w_{m-1} \to w_m \to u,<br /> \]

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 $.

Wystarczy teraz przyjąć

\[<br /> A = V, \quad B = U \cup \{w_1,\ldots,w_m\},<br /> \]

lub też

\[<br /> A = V \cup \{w_1,\ldots,w_m\}, \quad B = U,<br /> \]

aby uzyskać podział spełniający zadane warunki: przy każdym z tych dwóch określeń grupa $ A $ dominuje $ B $.

Dowód jest zakończony.

  • Wersja do wydrukuWersja do wydruku
  • Podziel się / Zapisz

Dodaj komentarz