XXXVII OM - III - Zadanie 5

Zawody matematyczne:

XXXVII OM, 1985-1986

Etap:

III

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.