Komentarz

LV OM - III - Zadanie 3

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

\[<br /> x_1 + x_2 +\ldots + x_n = {n \choose 2}.<br /> \]

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

\[<br /> {x_{1}\choose 2} + {x_{2}\choose 2} + \ldots + {x_{n}\choose 2}<br /> =\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).<br /> \]

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

    \[<br /> (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}.<br /> \]

    Zatem liczba trójek remisowych nie przekracza

    \[<br /> {n \choose 3}-\frac{n(n-1)(n-3)}{8}=\frac{n(n^{2}-1)}{24}.<br /> \]

    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
    \[<br /> (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}.<br /> \]

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

    \[<br /> {n \choose 3}-\frac{n(n-2)^2}{8}=\frac{n(n^{2}-4)}{24}.<br /> \]

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

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

Dodaj komentarz