LV OM - III - Zadanie 3

Zawody matematyczne:

LV OM, 2003-2004

Etap:

III

W pewnym turnieju wzięło udział $n$ zawodników $(n \geq 3)$ . Każdy grał z każdym dokładnie jeden raz, nie było remisów. Trójelementowy zbiór zawodników nazwiemy trójką remisową, jeśli można tak ponumerować tych trzech zawodników, że pierwszy wygrał z drugim, drugi z trzecim, a trzeci z pierwszym. Wyznaczyć największą liczbę trójek remisowych, jaka mogła się pojawić w turnieju.

Rozwiązanie

Zamiast wyznaczać największą liczbę trójek remisowych, wyznaczymy najmniejszą liczbę trójek, które nie są remisowe.

Ponumerujmy zawodników liczbami od 1 do $n$ i przyjmijmy, że zawodnik o numerze $i$ wygrał $x_i$ razy. Wówczas liczba wszystkich rozgrywek wynosi

$ x_1 + x_2 +\ldots + x_n = {n \choose 2}. $

Każda nieremisowa trójka jest wyznaczona jednoznacznie przez zawodnika, który wygrał z dwoma innymi zawodnikami tej trójki. Zatem zawodnik o numerze $i$ wyznacza $x_i \choose 2$ nieremisowych trójek, a liczba wszystkich nieremisowych trójek w turnieju wynosi

$ {x_{1}\choose 2} + {x_{2}\choose 2} + \ldots + {x_{n}\choose 2} =\frac{1}{2} \left(\sum_{i=1}^{n}x_{i}^{2} - \sum_{i=1}^{n}x_{i}\right) = \frac{1}{2} \left(\sum_{i=1}^{n}x_{i}^{2} - {n\choose 2} \right). $

W dalszej części rozwiązania rozpatrzymy dwa przypadki:

Liczba $n$ jest nieparzysta, tzn. $n = 2k + 1$ . Wówczas na mocy nierówności pomiędzy średnią kwadratową a średnią arytmetyczną uzyskujemy

$ (1)\qquad \frac{1}{2} \left(\sum_{i=1}^{n}x_{i}^{2} - {n\choose 2} \right) \geq \frac{1}{2} \left( \frac{1}{n} \left(\sum_{i=1}^{n}x_{i}\right)^{2} - {n\choose 2} \right) = \frac{n(n-1)(n-3)}{8}. $

Zatem liczba trójek remisowych nie przekracza

$ {n \choose 3}-\frac{n(n-1)(n-3)}{8}=\frac{n(n^{2}-1)}{24}. $

Powyższa liczba trójek remisowych wystąpi jedynie wtedy, gdy każdy zawodnik wygra dokładnie $k$ razy (w nierówności (1) zachodzi wtedy równość). Taki układ wyników rozgrywek możemy uzyskać w następujący sposób. Sadzamy zawodników przy okrągłym stole i zakładamy, że każdy z nich wygrał tylko z tymi zawodnikami, którzy siedzą po jego prawej stronie w odległości nie większej niż $k$ miejsc. Przy takim układzie rozgrywek każdy zawodnik wygrał dokładnie $k$ razy.
Liczba $n$ jest parzysta, tzn. $n = 2k$ . Wówczas $(x_i - k)(x_i - k + 1) \geq 0$ dla $i = 1,2,\ldots,n$ , skąd otrzymujemy $x_i^2 \geq (2k - 1)x_i - k(k - 1)$ . Zatem

$ (2) \frac{1}{2}\left(\sum_{i=1}^{n}x_{i}^{2} - {n\choose 2} \right) \geq \frac{1}{2}\left((2k-1)\sum_{i=1}^{n}x_{i}-nk(k-1)-{n \choose 2} \right) = \frac{n(n-2)^{2}}{8}. $

Stąd wynika, że liczba trójek remisowych nie przekracza

$ {n \choose 3}-\frac{n(n-2)^2}{8}=\frac{n(n^{2}-4)}{24}. $

Powyższa liczba trójek remisowych wystąpi jedynie wtedy, gdy każdy zawodnik wygra $k$ lub $k-1$ razy (w nierówności (2) zachodzi wtedy równość). Taki układ wyników rozgrywek możemy uzyskać w następujący sposób. Tak jak wyżej, sadzamy zawodników przy okrągłym stole i przyjmujemy, że każdy z nich wygrał z zawodnikami, którzy siedzą po jego prawej stronie w odległości nie większej niż $k-1$ miejsc. Wynik rozgrywki pomiędzy zawodnikami siedzącymi naprzeciwko siebie ustalamy dowolnie. W ten sposób każdy zawodnik wygrał $k$ lub $k-1$ razy.

Reasumując: największa liczba trójek remisowych, jaka może się pojawić w turnieju wynosi $\frac{1}{24}n(n^2 - 1)$ , jeśli $n$ jest liczbą nieparzystą oraz $\frac{1}{24}n(n^2 -4)$ , jeśli $n$ jest liczbą parzystą.