XLI OM - II - Zadanie 3

W turnieju szachowym każdy zawodnik rozegrał z każdym co najwyżej jedną partię, przy czym liczba partii rozegranych przez każdego z zawodników jest nie mniejsza od ustalonej liczby naturalnej $ n $. Udowodnić, że można podzielić zawodników na dwie grupy $ A $ i $ B $ w taki sposób, by liczba partii rozegranych przez każdego gracza grupy $ A $ z graczami grupy $ B $ była nie mniejsza niż $ n/2 $ i jednocześnie liczba partii rozegranych przez każdego gracza grupy $ B $ z graczami grupy $ A $ była nie mniejsza niż $ n/2 $.

Rozwiązanie

Weźmy pod uwagę dowolny podział $ (A,B) $ zbioru wszystkich zawodników na dwa rozłączne podzbiory $ A $ i $ B $. Niech $ q(A,B) $ oznacza liczbę wszystkich rozegranych partii, w których jeden z przeciwników należał do zbioru $ A $, a drugi - do $ B $. Ponieważ liczba wszystkich możliwych podziałów $ (A,B) $ jest skończona, istnieje zatem taki podział, dla którego wartość $ q(A,B) $ jest maksymalna. Ustalmy ten podział; jeśli maksimum to jest osiągane dla kilku różnych podziałów, wybieramy dowolny z nich. W dalszym ciągu $ (A,B) $ będzie oznaczać nasz wybrany podział (dla którego wielkość $ q $ osiąga maksimum).

Udowodnimy, że podział ten spełnia warunek postulowany w tezie zadania.

Przypuśćmy, wbrew temu stwierdzeniu, że na przykład w zbiorze $ A $ znajduje się zawodnik, który z graczami grupy $ B $ rozegrał mniej niż $ n/2 $ partii; oznaczmy go literą $ a $. Przenosimy gracza $ a $ z grupy $ A $ do $ B $. Zbiór $ A $ ,,uszczuplony'' o zawodnika $ a $ oznaczmy symbolem $ A' $; zbiór $ B $ ,,wzbogacony'' o zawodnika $ a $ oznaczmy przez $ B' $. Tak więc

\[<br /> A' = A \ \{a\}, \quad B' = B\ \{a\}.<br /> \]

Przyjmijmy, że zawodnik $ a $ rozegrał $ k_A $ partii z graczami grupy $ A $ oraz $ k_B $ partii z graczami grupy $ B $. Zachodzi równość

\[<br /> q(A\,B')-q(A,B) = k_A-k_B,<br /> \]

wynikająca stąd, że wszystkie partie rozegrane bez udziału zawodnika $ a $, uwzględnione przy obliczeniu $ q(A,B) $, wchodzą także do obliczenia $ q(A',B') $ (i na odwrót), więc przy obliczaniu różnicy $ q(A',B') - q(A,B) $ znoszą się. Z założenia wynika, że $ k_A + k_B \geq n $, natomiast uczynione przez nas przypuszczenie mówi, że $ k_B < n/2 $. Stąd $ k_A > n/2 $. Tak więc $ k_A - k_B > 0 $ i w konsekwencji

\[<br /> q(A',B')-q(A,B)>0.<br /> \]

Jest to jednak sprzeczne z określeniem podziału $ (A,B) $ jako tego, dla którego wielkość $ q(A,B) $ osiąga maksimum.

Podobną sprzeczność uzyskamy wychodząc z przypuszczenia, że w grupie $ B $ znajdzie się zawodnik, który z graczami grupy $ A $ rozegrał mniej niż $ n/2 $ partii (rola zbiorów $ A $ i $ B $ jest w rozważanym zagadnieniu symetryczna).

Uzyskana sprzeczność dowodzi tezy zadania.

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

Komentarze

Dodaj nową odpowiedź