XLVI OM - I - Zadanie 4

Zawody matematyczne:

XLVI OM, 1994-1995

Etap:

W pewnej szkole 64 uczniów bierze udział w pięciu olimpiadach przedmiotowych. W każdej z tych olimpiad uczestniczy co najmniej 19 uczniów tej szkoły; żaden z nich nie jest uczestnikiem więcej niż trzech olimpiad. Udowodnić, że jeżeli każde trzy olimpiady mają wspólnego uczestnika, to pewne dwie mają ich co najmniej pięciu.

Rozwiązanie

Oznaczmy olimpiady symbolami $A$ , $B$ , $C$ , $D$ , $E$ . Wyobraźmy sobie tabelę mającą $64$ wierszy, odpowiadających uczniom, oraz $25$ kolumn opatrzonych następującymi nagłówkami:

$ A, B, C, D, E,\quad AB, AC, AD, AE, BC, BD, BE, CD, CE, DE, $

$ ABC, ABD, ABE, ACD, ACE, ADE, BCD, BCE, BDE, CDE. $

W kolumnie z nagłówkiem $X$ , reprezentującej olimpiadę $X \in \{A,B,C,D,E\}$ , w rubryce każdego ucznia wpisujemy $1$ , jeśli uczestniczy on w tej olimpiadzie, a $0$ jeśli nie uczestniczy. W kolumnie $XY$ piszemy $-1$ , jeśli dany uczeń uczestniczy w obu olimpiadach $X$ i $Y$ , a $0$ w przeciwnym przypadku. Wreszcie w kolumnie $XYZ$ piszemy znów $1$ , jeśli uczeń uczestniczy we wszystkich trzech olimpiadach $X$ , $Y$ i $Z$ , a $0$ w przeciwnym przypadku.

Suma liczb w każdej z pierwszych pięciu kolumn $(A, B, C, D, E)$ jest większa lub równa $19$ (bo w każdej olimpiadzie uczestniczy co najmniej $19$ uczniów). Sumy liczb w następnych dziesięciu kolumnach ( $AB$ , $AC$ , $\ldots$ , $DE$ ) oznaczmy kolejno przez $s_1,s_2,\ldots,s_{10}$ . Jeżeli wreszcie, zgodnie z założeniem, każde trzy olimpiady mają wspólnego uczestnika, to w każdej z ostatnich dziesięciu kolumn $(ABC, \ldots, CDE)$ jest co najmniej jedna jedynka, więc suma liczb w każdej z tych kolumn jest większa lub równa $1$ . Wobec tego suma wszystkich liczb w tabeli - oznaczmy ją przez $s$ - spełnia oszacowanie

$ (1) \qquad \quad s \geq 5 \cdot 19 + (s_1+s_2+s_3 + s_4 + s_5+s_6 + s_7 + s_8+s_9 + s_{10}) + 10 \cdot 1. $

Zauważmy teraz, że suma liczb w każdym wierszu wynosi $1$ . Istotnie: jeśli uczeń uczestniczy w dokładnie jednej olimpiadzie, to w jego wierszu znajduje się jedna plus jedynka, poza tym zera; jeśli uczestniczy w dokładnie dwóch olimpiadach ( $X$ i $Y$ ), to są tam dwie plus jedynki (w kolumnach $X$ i $Y$ ) oraz jedna minus jedynka (w kolumnie $XY$ ); a jeśli uczestniczy w dokładnie trzech olimpiadach ( $X$ , $Y$ , $Z$ ), to mamy cztery plus jedynki (w kolumnach $X$ , $Y$ , $Z$ i $XYZ$ ) oraz trzy minus jedynki (w kolumnach $XY$ , $XZ$ , $YZ$ ). Wobec tego suma wszystkich liczb w tabeli wynosi $64$ .

Podstawiając $s = 64$ do nierówności (1) dostajemy oszacowanie

$ s_1+s_2 + s_3+s_4 + s_5+s_6+s_7 + s_8 + s_9 + s_{10} \leq 64 - (5 \cdot 19 + 10 \cdot 1) = -41. $

Wynika z niego, że co najmniej jedna z liczb $s_i$ jest mniejsza od $-4$ , czyli spełnia nierówność $s_i \leq -5$ (są to bowiem liczby całkowite). To znaczy, że w kolumnie, której wyrazy sumują się do wartości $s_i$ , jest co najmniej pięć minus jedynek. To znaczy, że para olimpiad, reprezentowana przez tę kolumnę, ma co najmniej pięciu wspólnych uczestników.

Uwaga. Gdyby odrzucić założenie, że żaden uczeń nie jest uczestnikiem więcej niż trzech olimpiad, wówczas należałoby rozszerzyć tabelę o dalsze kolumny: pięć kolumn reprezentujących czwórki olimpiad ( $ABCD$ , $ABCE$ , $ABDE$ , $ACDE$ , $BCDE$ ) oraz jedną kolumnę odpowiadającą pełnej piątce olimpiad ( $ABCDE$ ).

W kolumnie czwórkowej $TXYZ$ , w rubryce każdego ucznia, wpisujemy znów $-1$ , jeśli uczestniczy on we wszystkich czterech olimpiadach $T$ , $X$ , $Y$ , $Z$ , a $0$ jeśli nie uczestniczy; wreszcie w ostatniej kolumnie piszemy $1$ , jeśli uczeń uczestniczy we wszystkich pięciu olimpiadach, a $0$ w przeciwnym przypadku. W każdym wierszu tak rozszerzonej tabeli suma liczb nadal wynosi $1$ . Można się o tym przekonać, rozpatrując pominięte wcześniej dwie sytuacje: uczeń uczestniczy w dokładnie czterech olimpiadach oraz uczeń uczestniczy we wszystkich pięciu olimpiadach. Suma liczb w całej tabeli będzie więc nadal równa liczbie wierszy, czyli liczbie wszystkich uczniów, biorących udział w co najmniej jednej olimpiadzie.

Jeśli więc zbiór wszystkich uczniów (z owej szkoły), którzy uczestniczą w olimpiadzie $A$ , oznaczymy tym samym symbolem $A$ , i podobne znaczenie nadamy symbolom $B$ , $C$ , $D$ i $E$ , to w wyniku przeprowadzonego rozumowania otrzymamy równość:

$ \begin{split} | A \cup B \cup C \cup D \cup E | = & (|A| + |B| + |C| + |D| + |E|)-\\ & - (|A \cap B| + \ldots + |D \cap E|) +\\ & + (|A \cap B \cap C| + \ldots + |C \cap D \cap E|) -\\ & - (|A \cap B \cap C \cap D)| + \ldots + |B \cap C \cap D \cap E|) +\\ & + |A \cap B \cap C \cap D \cap E| \end{split} $

(przez $|X|$ oznaczamy liczbę elementów zbioru skończonego $X$ ; w nawiasach w drugiej, trzeciej i czwartej linijce powyższego wzoru znajdują się składniki odpowiadające wszystkim parom, wszystkim trójkom i wszystkim czwórkom zbiorów z rodziny $\{A,B,C,D,E\}$ ). Oczywiście szkoła, uczniowie, olimpiady — to tylko barwne przybranie dla treści matematycznej. Otrzymana równość zachodzi dla dowolnych pięciu zbiorów skończonych $A$ , $B$ , $C$ , $D$ , $E$ .

Analogiczną równość można napisać dla dowolnego skończonego układu zbiorów skończonych; dla dwóch zbiorów ma ona prostą i dobrze znaną postać: $|A \cup B| = |A| + |B| - | A \cap B |$ ; ogólnie zaś, dla $n$ zbiorów, jej zapis jest trochę trudno czytelny:

$ (2) \qquad \quad |A_1 \cup \ldots \cup A_n| = \sum_{k=1}^n \left((-1)^{k+1} \sum_{1 \leq i_1 < \ldots < i_k \leq n} |A_{i_1} \cap \ldots \cap A_{i_k}|\right). $

Jest to tak zwany wzór włączeń i wyłączeń (inaczej: formuła sita). Poprzednie rozumowanie stanowi jego dowód dla $n = 5$ ; w podobny sposób można go udowodnić dla dowolnej liczby naturalnej $n$ . (Trzeba rozważać tabelę składającą się z $2^n$ kolumn, podzieloną na bloki złożone z ${{n}\choose{1}}$ , ${{n}\choose{2}}$ , \ldots, ${{n}\choose{n}}$ kolumn, i wpisywać w kolejnych blokach, na przemian, jedynki i minus jedynki, w zależności od tego, czy element reprezentowany przez poszczególny wiersz tabeli należy do wszystkich $k$ zbiorów, odpowiadających danej kolumnie, czy nie należy). Suma liczb w każdym wierszu takiej tabeli stale wynosi $1$ . Proponujemy, by Czytelnik spróbował zastanowić się, dlaczego tak jest. (Wskazówka: ${{m}\choose{1}} - {{m}\choose{2}} +\ldots+(-1)^{m+1} {{m}\choose{m}} =1$ .)

Dowód wzoru (2) można także przeprowadzić przez indukcję względem $n$ ; również i taki dowód pozostawiamy Czytelnikowi jako ciekawe ćwiczenie.