Komentarz

XXXVII OM - III - Zadanie 5

W turnieju szachowym uczestniczy $ 2n $ ($ n > 1 $) zawodników, przy czym każdych dwóch spośród nich rozgrywa między sobą co najwyżej jedną partię. Dowieść, że taki przebieg rozgrywek, w którym żadna trójka uczestników nie rozgrywa trzech partii między sobą jest możliwy wtedy i tylko wtedy, gdy liczba wszystkich partii rozegranych w turnieju nie przekracza $ n^2 $.

Rozwiązanie

Mamy do udowodnienia równoważność następujących dwóch stwierdzeń $ A $ i $ B $ (dla danych liczb naturalnych $ m $ i $ n $, $ n > 1 $):

A. Istnieje możliwość takiej organizacji rozgrywek turnieju z udziałem $ 2n $ zawodników, że

  • $ A_1 $) każdy z każdym gra co najwyżej jedną partię,
  • $ A_2 $) żadna trójka nie rozgrywa trzech partii między sobą,
  • $ A_3 $) łączna liczba partii w turnieju wynosi $ m $.

B. Liczby $ m $ i $ n $ spełniają nierówność $ m \leq n^2 $.

Dowód implikacji $ B \Longrightarrow A $. Uczestników turnieju dzielimy w dowolny sposób na dwie grupy po $ n $ zawodników. Liczba par, w których partnerzy należą do różnych grup, wynosi $ n^2 $. Wybieramy dowolnie $ m $ spośród tych par i przeprowadzamy rozgrywki w wybranych parach. Spełnienie warunków $ A_1 $, $ A_2 $, $ A_3 $ jest oczywiste.

Dowód implikacji $ A \Longrightarrow B $. Stosujemy indukcję względem $ n $. Gdy $ n = 2 $, mamy $ 4 $ graczy i $ 6 $ możliwych par. Gdyby liczba rozgrywanych partii przekraczała $ 4 $, znaczyłoby to, że rozgrywane są wszystkie możliwe spotkania z wyjątkiem co najwyżej jednego; musi wtedy utworzyć się ,,trójkąt spotkań'' (a nawet dwa takie trójkąty).

Załóżmy, że twierdzenie jest prawdziwe dla pewnego $ n \geq 2 $ i przypuśćmy, że został zorganizowany turniej z udziałem $ 2(n + 1) $ zawodników tak, że spełnione są warunki $ A_1 $, $ A_2 $, $ A_3 $. Mamy pokazać, że $ m \leq (n + 1)^2 $. Wybierzmy dowolnych dwóch zawodników rozgrywających partię między sobą i nazwijmy ich $ X $ i $ Y $. Liczba partii rozgrywanych między pozostałymi $ 2n $ zawodnikami nie przekracza $ n^2 $, w myśl założenia indukcyjnego. Niech $ x $ będzie liczbą partii rozgrywanych przez gracza $ X $ (nie licząc spotkania z $ Y $), a $ y $ - liczbą partii rozgrywanych przez $ Y $ (nie licząc spotkania z $ X $). Wówczas $ x + y \leq 2n $; w przeciwnym razie $ X $ i $ Y $ mieliby wspólnego przeciwnika i powstałby ,,trójkąt spotkań'', wbrew warunkowi $ A_2 $. Uwzględniając jeszcze mecz pomiędzy $ X $ i $ Y $ widzimy, że łączna liczba spotkań w turnieju nie przekracza $ n^2 + 2n + 1 $ czyli $ (n + 1)^2 $. Kończy to dowód indukcyjny.

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

Dodaj komentarz