XXXVIII OM - I - Zadanie 12

W turnieju uczestniczy $ n $ graczy. Każdy z nich rozgrywa z każdym dokładnie jeden mecz. W każdym meczu gracz zdobywa 0, 1 lub 2 punkty w zależności od tego, czy przegra, zremisuje lub wygra. Ciąg $ (a_1, a_2, \ldots , a_n) $ nazywamy wynikiem turnieju, jeśli możliwy jest przebieg rozgrywek, przy którym $ a_i $ jest sumą punktów zdobytych przez $ i $-tego gracza ($ i = 1, 2, \ldots, n $). Wykazać, że ciąg liczb całkowitych nieujemnych $ (b_1, b_2, \ldots, b_n) $ jest wynikiem turnieju wtedy i tylko wtedy, gdy $ \sum_{i=1}^n b_i = n(n—l) $ oraz dla każdego niepustego podzbioru $ A $ zbioru liczb $ \{1, 2, \ldots, n\} $ spełniona jest nierówność:

\[<br /> \sum_{i\in A} b_i \geq k_A(k_A-1),<br /> \]

gdzie $ k_A $ jest liczbą elementów zbioru $ A $.

Rozwiązanie

Ciąg liczb całkowitych $ (b_1, \ldots ,b_n $) spełniający podane warunki:

\[<br /> (1) \qquad \sum_{i=1}^n b_i =n(n-1),<br /> \]
\[<br /> (2) \qquad \sum_{i\in A} b_i \geq k_A(k_A-1) \quad \textrm{dla } A\subset \{1,\ldots, n \},\ A\neq \emptyset.<br /> \]

będziemy nazywać ciągiem dopuszczalnym (długości $ n $); zauważmy, że warunek (2) pociąga za sobą nieujemność liczb $ b_i $ (wystarczy wziąć pod uwagę jednoelementowe zbiory $ A $).

Mamy dowieść, że ciąg jest wynikiem turnieju wtedy i tylko wtedy, gdy jest dopuszczalny. Implikacja ,,tylko wtedy'' jest oczywista: jeśli ciąg $ (b_1, \ldots ,b_n) $ jest wynikiem turnieju, to spełnia podane warunki; warunek (1) wynika z ... warunek (2) zaś z tego, że w samych tylko meczach między zawodnikami o numerach $ i \in A $ rozdzielono $ 2 \cdot k_A(k_A -1)/2 $ punktów. Przedstawimy kilka dowodów implikacji przeciwnej:

Twierdzenie. Każdy ciąg dopuszczalny jest wynikiem turnieju.

W dowodach będziemy się czasem posługiwali ,,tabelą wyników''. Rozpatrujemy turniej z udziałem $ n $ graczy. Dla $ i,j \in \{1, \ldots, n\} $, $ i \neq j $, niech $ r_{ij} $ oznacza liczbę punktów zdobytych przez gracza $ i $ w meczu z graczem $ j $.

Tablicę (macierz) kwadratową (bez przekątnej)

\[<br /> (3) \qquad<br /> \begin{array}{|c|c|c|c|}<br /> \hline \vphantom{\bigg(} \times &r_{12}&\ldots&r_{1n}\\<br /> \hline \vphantom{\bigg(} r_{21}&\times &\ldots&r_{2n}\\<br /> \hline \vphantom{\bigg(}\vdots&\vdots&\ddots&\vdots\\<br /> \hline \vphantom{\bigg(} r_{n1}&r_{n2}&\ldots&\times \\<br /> \hline<br /> \end{array}<br /> \qquad<br /> \left(<br /> \begin{array}{l}<br /> r_{ij} \in \{0, 1, 2\}\\<br /> i,j \in \{1, \ldots, n\} i \neq j\\<br /> r_{ij}+r_{ji}=2<br /> \end{array}<br /> \right)<br /> \]

będziemy nazywali tabelą wyników turnieju. Ciąg $ (a_1, \ldots, a_n) $ jest więc wynikiem turnieju wtedy i tylko wtedy, gdy istnieje tabela (3) (o wyrazach $ r_{ij} $) spełniających podane warunki) taka, że $ a_i $ jest sumą elementów z $ i $--tego wiersza:

\[<br /> (4) \qquad a_i = \sum_{\substack{j=1\\ j \neq i}}^n r_{ij} \quad \textrm{dla } i = 1, \ldots, n.<br /> \]

Przystępujemy do dowodu sformułowanego wyżej twierdzenia.

Niech będzie dany dowolny ciąg dopuszczalny $ (b_1, \ldots, b_n) $ (ustalonej długości $ n $). Spośród wszystkich ciągów $ (a_1, \ldots ,a_n) $ będących wynikami turnieju wybierzmy taki, dla którego wartość sumy

\[<br /> (19) \qquad \sum_{i=1}^n |a_i-b_i|<br /> \]

jest możliwie najmniejsza. Należy pokazać, że ta minimalna wartość wynosi $ 0 $.

Przypuśćmy więc, że tak nie jest, czyli że wybrany ciąg $ (a_1, \ldots, a_n) $ nie jest identyczny z ciągiem $ (b_1, \ldots, b_n) $. Ponieważ $ a_1+ \ldots +a_n = b_1+ \ldots + +b_n $, znajdzie się numer $ p $ taki, że

\[<br /> (20) \qquad a_p < b_p.<br /> \]

Rozważmy tabelę wyników (3), o wyrazach $ r_ij $, realizującą wynik $ (a_1, \ldots, a_n) $; zachodzi więc wzór (4). Określimy teraz pewien zbiór numerów $ A \subset \{1, \ldots, n\} $. Do zbioru $ A $ zaliczymy liczbę $ p $ oraz wszystkie te numery $ i \neq p $, dla których istnieje liczba naturalna $ m $ oraz ciąg różnych numerów $ (i_0, \ldots, i_m) $ taki, że

\[<br /> i_0=p,\quad i_m=i<br /> \]
\[<br /> r_{i_{k-1}i_k} \geq 1 \quad \textrm{dla } k=1, \ldots, m.<br /> \]

Zauważmy, że jeśli $ i\in A $ oraz jest numerem takim, że $ r_{ij} \geq 1 $, to $ j\in A $. Zatem

\[<br /> r_{ij} = 0\quad \textrm{dla } i\in A,\ j \notin A,<br /> \]

więc zgodnie z wzorem (4) mamy

\[<br /> (21) \qquad a_i= \sum_{j\in A \setminus \{i\}} r_{ij} \quad \textrm{dla } i \in A.<br /> \]

W rozpatrywanym turnieju ograniczmy na chwilę uwagę tylko do meczów rozegranych między zawodnikami o numerach należących do $ A $. Tabela wyników tego mini-turnieju powstaje z tabeli (3) przez wykreślenie wierszy i kolumn o numerach spoza $ A $. Suma elementów wiersza odpowiadającego w tak zredukowanej tabeli zawodnikowi o numerze i równa się nadal $ a_i $, na mocy równości (21). Zatem suma wszystkich elementów tej tabeli wynosi $ \sum_{i\in A} a_i $. Jednocześnie suma ta równa się, $ k_A(k_A-1) $, bo tyle punktów rozdzielono w rozważanym mini-turnieju. Tak więc

\[<br /> \sum_{i\in A}a_i = k_A(k_A-1).<br /> \]

Ciąg $ (b_1,\ldots , b_n) $, jako dopuszczalny, spełnia warunek (2). Wynika stąd, że

\[<br /> \sum_{i\in A}b_i \geq \sum_{i\in A}a_i.<br /> \]

a skoro $ a_p > b_p $, musi zachodzić dla pewnego $ q \in A $ nierówność

\[<br /> (22) \qquad a_q < b_q.<br /> \]

Zgodnie z definicją zbioru $ A $ istnieje ciąg numerów $ (i_0, \quad , i_m) $ taki, że

\[<br /> i_0=p, \quad i_m=q,<br /> \]
\[<br /> r_{i_{k-1}i_k} \geq 1 \quad \textrm{dla } k=1, \ldots, m.<br /> \]

Ostatni warunek oznacza po prostu, że zawodnik o numerze $ i_{k-1} $ nie przegrał w meczu z zawodnikiem o numerze $ i_k $ ($ k = 1, \ldots , m $).

Wracamy teraz do pełnej tabeli (3) i reprezentowanego przez nią przebiegu rozgrywek, i dokonujemy w tym przebiegu zmiany następującej: dla każdego $ k \in \{1, \ldots, m\} $ podwyższamy wynik meczu pomiędzy $ i_{k-1} $ a $ i_k $ o $ 1 $ punkt na korzyść $ i_k $. Wyników pozostałych meczów nie zmieniamy. Oznaczając przez $ (a'_1,\ldots, a'_n) $ wynik turnieju przy nowym przebiegu rozgrywek mamy

\[<br /> (23) \qquad \begin{split}<br /> &a'_p=a_p-1, \quad a'_q=a_q+1\\<br /> &a'_i=a_i \quad \textrm{dla } i \neq p,q.<br /> \end{split}<br /> \]

Istotnie; patrząc na ciąg numerów $ p = i_0, i_1, i_2, \ldots, i_{m-1},i_m=q $ widzimy, że zawodnik o numerze $ i_k $ ($ 1 \leq k \leq m-1 $) jest uczestnikiem dwóch meczów o zmienianych wynikach, przy czym doświadcza jednej zmiany na swoją korzyść, a jednej na niekorzyść; niezrównoważone zostają tylko zmiany u numerów skrajnych: $ p $i $ q $; dla numerów, które w ciągu $ (i_0, \ldots, i_m) $ nie występują, w ogóle nic się nie zmienia. Stąd słuszność związków (23).

Uwzględniając nierówności (20) i (22) otrzymujemy z tych związków zależności

\[<br /> \begin{split}<br /> \sum^n_{i=1} |a'_i-b_i|&=\\<br /> &=|a'_p-b_p|+a'_q-b_q|+\sum_{i\neq p,q}|a'_i-b_i|=\\<br /> &=|a_p-b_p-1|+|a_q-b_q+1|+\sum_{i\neq p,q}|a_i-b_i|<\\<br /> &<|a_p-b_p|+a_q-b_q|+\sum_{i\neq p,q}|a_i-b_i|=\\<br /> &=\sum^n_{i=1} |a_i-b_i|<br /> \end{split}<br /> \]

- wbrew minimalności sumy (19).
Dowodzi to niesłuszności przypuszczenia, że minimalna wartość tej sumy jest dodatnia. Musi być ona zerem, a zatem ciąg $ (b_1, \ldots ,b_n) $ jest jednym z możliwych wyników turnieju.

Uwaga 2. Śledząc podane rozwiązanie, wygodnie jest wyobrazić sobie $ n $-kąt z poprowadzonymi wszystkimi przekątnymi (tzw. graf pełny); jego wierzchołki reprezentują graczy, a boki i przekątne (krawędzie grafu) — mecze między zawodnikami. Gdy dany jest przebieg turnieju, opatrujemy te odcinki strzałkami (powstaje ,,graf skierowany''): jeśli $ i $, $ j $ są numerami dwóch zawodników, a mecz między nimi zakończył się zwycięstwem zawodnika $ i $, prowadzimy strzałkę od wierzchołka $ i $ (czyli wierzchołka reprezentującego zawodnika $ i $) do wierzchołka $ j $: $ i\rightarrow j $; remis oznaczamy strzałką dwustronną: $ i \leftrightarrow j $ A zatem:

\[<br /> r_{ij}=\left\{<br /> \begin{split}<br /> &2 \Leftrightarrow \textrm{mamy strzałkę } i\rightarrow j\\<br /> &1 \Leftrightarrow \textrm{mamy strzałkę } i\leftrightarrow j\\<br /> &0 \Leftrightarrow \textrm{mamy strzałkę } i\leftarrow j<br /> \end{split}<br /> \right.<br /> \]

Określony w rozwiązaniu zbiór $ A $ interpretuje się jako zbiór tych wierzchołków $ i $, do których można dojść z wierzchołka $ p $ poruszając się wzdłuż krawędzi grafu zawsze w kierunku zgodnym z kierunkiem strzałek (po strzałkach dwustronnych można iść w obie strony.) Przeprowadzona następnie modyfikacja przebiegu turnieju polega na tym, że w ciągu krawędzi:
$ p \frac{\hphantom{\to}}{\hphantom{\to}} i_1 \frac{\hphantom{\to}}{\hphantom{\to}} i_2 \frac{\hphantom{\to}}{\hphantom{\to}} \ldots \frac{\hphantom{\to}}{\hphantom{\to}}i_{m-1} \frac{\hphantom{\to}}{\hphantom{\to}} q $ każdą strzałkę $ \rightarrow $ (skierowaną zgodnie z kierunkiem drogi od $ p $ do $ q $) zastępujemy strzałką $ \leftrightarrow $, a każdą strzałkę $ \leftrightarrow $ zastępujemy strzałką $ \leftarrow $ (skierowaną przeciwnie).

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