XLI OM - II - Zadanie 3

Zawody matematyczne:

XLI OM, 1989-1990

Etap:

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

$ A' = A \ \{a\}, \quad B' = B\ \{a\}. $

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

$ q(A\,B')-q(A,B) = k_A-k_B, $

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

$ q(A',B')-q(A,B)>0. $

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.