XXXVII OM - II - Zadanie 2

Zawody matematyczne:

XXXVII OM, 1985-1986

Etap:

W turnieju szachowym uczestniczy 66 zawodników, każdy z każdym rozgrywa jedną partią, rozgrywki odbywają się w czterech miastach. Udowodnić, że pewna trójka zawodników rozgrywa wszystkie partie między sobą w tym samym mieście.

Rozwiązanie

Wybierzmy jednego z zawodników, nazwijmy go $Z_1$ . Ma on do rozegrania $65$ partii, a więc co najmniej $17$ partii rozgrywa w jednym mieście. Oznaczmy to miasto symbolem $M_1$ . Weźmy pod uwagę przeciwników $Z_1$ w spotkaniach rozgrywanych w $M_1$ . Jest ich nie mniej niż $17$ . Jeśli istnieje wśród nich para rozgrywająca partię między sobą także w $M_1$ , to wespół z zawodnikiem $Z_1$ tworzą oni trójkę grającą ,,trójkąt spotkań'' w jednym mieście i twierdzenie jest udowodnione. Załóżmy wobec tego, że cała ta grupa $17$ (lub więcej) szachistów gra wszystkie mecze między sobą w pozostałych trzech miastach. Wybierzmy jednego z tej grupy i nazwijmy go $Z_2$ . Ma on w tej grupie co najmniej $16$ przeciwników, a więc z co najmniej $6$ z nich musi grać w jednym mieście, które oznaczymy symbolem $M_2$ . Jeśli któraś para wśród nich rozgrywa swoją partię także w $M_2$ , daje to ,,trójkąt spotkań'' w $M_2$ . No to przypuśćmy, że tak nie jest; znaczy to, że rozważana grupa $6$ (lub więcej) szachistów rozgrywa partie między sobą w pozostałych dwóch miastach. Powtarzamy więc jeszcze raz to samo rozumowanie. Wybieramy z tej grupy jednego zawodnika $Z_3$ i zauważamy, że mając w tej grupie co najmniej $5$ przeciwników, musi z co najmniej $3$ z nich grać w jednym mieście $M_3$ . Jeśli jest wśród nich para rozgrywająca swoją partię w $M_3$ , to wraz z zawodnikiem $Z_3$ tworzą oni trójkę grającą ,,trójkąt spotkań'' w $M_3$ . W przeciwnym razie cała ta grupa $3$ (lub więcej) szachistów rozgrywa spotkania między sobą w ostatnim pozostałym mieście $M_4$ . Tym samym twierdzenie zostało udowodnione.

Uwaga. Podany dowód ma charakter indukcyjny, składa się z kilku kroków, w których powielany jest ten sam schemat rozumowania. To spostrzeżenie prowadzi do następującego naturalnego uogólnienia; wygodnie formułować je w języku tzw. teorii grafów.

Niech $(n_k)$ będzie ciągiem liczb określonym wzorem rekurencyjnym $n_1 = 2$ , $n_k = kn_{k-1}+1$ dla $k \geq 2$ . Przypuśćmy, że $G$ jest zbiorem $n$ punktów w przestrzeni, $n > n_k$ , i że każdy z odcinków łączących punkty zbioru $G$ został pokolorowany jednym z $k$ kolorów. Wówczas istnieją w zbiorze $G$ trzy punkty takie, że trójkąt o wierzchołkach w tych punktach ma wszystkie boki jednego koloru.

(Początkowymi wyrazami ciągu $(n_k)$ są liczby $2$ , $5$ , $16$ , $65$ , czyli liczby pojawiające się w rozwiązaniu zadania; dla $k = 4$ otrzymujemy twierdzenie dane w zadaniu, przy czym oczywiście szachistów należy interpretować jako punkty zbioru $G$ , rozgrywane partie jako odcinki, a miasta jako kolory).

Sformułowane przed chwilą ogólne twierdzenie łatwo udowodnić przez indukcję stosując schemat rozumowania użyty w rozwiązaniu zadania.

Warto nadmienić, że ciąg $(n_k)$ określony podanym wzorem rekurencyjnym nie jest optymalny; jeśli $k \geq 4$ , to istnieją liczby $n \leq n_k$ takie, że dla dowolnego $n$ -elementowego zbioru punktów $G$ prawdziwa jest konkluzja twierdzenia (z $k$ kolorami); w szczególności, twierdzenie z zadania pozostaje prawdziwe przy zastąpieniu liczby $66$ liczbą $65$ . Nie jest jednak znany żaden wzór dający nietrywialne dolne ograniczenie dopuszczalnych wartości $n$ , ani asymptotyczne zachowanie tych minimalnych wartości, gdy $k \to \infty$ .