XXXVIII OM - I - Zadanie 12

Zawody matematyczne:

XXXVIII OM, 1986-1987

Etap:

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ść:

$ \sum_{i\in A} b_i \geq k_A(k_A-1), $

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:

$ (1) \qquad \sum_{i=1}^n b_i =n(n-1), $

$ (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. $

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)

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

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:

$ (4) \qquad a_i = \sum_{\substack{j=1\\ j \neq i}}^n r_{ij} \quad \textrm{dla } i = 1, \ldots, n. $

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

$ (19) \qquad \sum_{i=1}^n |a_i-b_i| $

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

$ (20) \qquad a_p < b_p. $

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

$ i_0=p,\quad i_m=i $

$ r_{i_{k-1}i_k} \geq 1 \quad \textrm{dla } k=1, \ldots, m. $

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

$ r_{ij} = 0\quad \textrm{dla } i\in A,\ j \notin A, $

więc zgodnie z wzorem (4) mamy

$ (21) \qquad a_i= \sum_{j\in A \setminus \{i\}} r_{ij} \quad \textrm{dla } i \in A. $

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

$ \sum_{i\in A}a_i = k_A(k_A-1). $

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

$ \sum_{i\in A}b_i \geq \sum_{i\in A}a_i. $

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

$ (22) \qquad a_q < b_q. $

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

$ i_0=p, \quad i_m=q, $

$ r_{i_{k-1}i_k} \geq 1 \quad \textrm{dla } k=1, \ldots, m. $

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

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

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

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

- 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:

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

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