XXXVII OM - II - Zadanie 2

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

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

Komentarze

Dodaj nową odpowiedź