XLV OM - I - Zadanie 9

Zawody matematyczne:

XLV OM, 1993-1994

Etap:

W konferencji bierze udział $2n$ osób. Każdy uczestnik konferencji ma wśród pozostałych uczestników co najmniej $n$ znajomych. Udowodnić, że wszystkich uczestników konferencji można zakwaterować w pokojach dwuosobowych tak, by każdy uczestnik mieszkał ze swoim znajomym.

Rozwiązanie

W zadaniu zakłada się milcząco, że jeśli pewna osoba zna inną, to ta druga osoba zna pierwszą, oraz że nikt nie jest swoim własnym znajomym.

Niech $m$ będzie maksymalną liczbą rozłącznych par znajomych, jakie można utworzyć spośród uczestników konferencji. Zadanie sprowadza się do wykazania, że $m = n$ . Przypuśćmy więc, że $m < n$ i niech $P_1,\ldots, P_m$ będzie układem $m$ rozłącznych par znajomych. Zbiór pozostałych uczestników konferencji (tych, którzy nie znaleźli się w żadnej z par $P_1,\ldots ,P_m$ ) oznaczmy przez $Q$ .

Weźmy pod uwagę dowolnych dwóch uczestników $A$ i $B$ ze zbioru $Q$ . Żaden z nich nie ma znajomego w zbiorze $Q$ (gdyby miał, utworzyłby wraz z tym znajomym ( $m + 1$ )--szą parę, wbrew maksymalności $m$ ). Zatem - w myśl założenia - zarówno uczestnik $A$ , jak i $B$ , ma w zbiorze $P_1\cup \ldots \cup P_m$ co najmniej $n$ znajomych.

Każdemu uczestnikowi konferencji przyporządkujmy liczbę $2$ , $1$ lub $0$ , w zależności od tego, czy zna on obie osoby $A$ i $B$ , dokładnie jedną z nich, czy żadną. Dla $i = 1,\ldots,m$ oznaczmy przez $s_i$ sumę liczb przyporządkowanych dwóm uczestnikom konferencji, tworzącym parę $P_i$ . Z konkluzji ostatniego zdania w poprzednim akapicie wynika nierówność $s_1 + \ldots + s_m \geq 2n$ , bowiem suma $s_1 + \ldots + s_m$ wyraża liczbę wszystkich ,,połączeń'' (w sensie relacji ,,bycia znajomym'') między elementami zbioru $P_1 \cup \ldots\cup P_m$ i elementami zbioru $\{A,B\}$ .

Gdyby wszystkie składniki sumy $s_1 + \ldots + s_m$ były mniejsze lub równe $2$ , wartość tej sumy nie przekraczałaby $2m$ , a więc byłaby mniejsza od $2n$ . W takim razie co najmniej jeden składnik jest większy od $2$ . Nie tracąc ogólności przyjmijmy, że $s_m \geq 3$ (kolejność ponumerowania można zmienić w razie potrzeby). Oznaczmy uczestników tworzących parę $P_m$ przez $C$ i $D$ . Suma przyporządkowanych im liczb (czyli $s_m$ ) wynosi $3$ lub $4$ , a to znaczy, że co najmniej jeden z tych uczestników zna obie osoby $A$ i $B$ , a drugi zna co najmniej jedną z tych osób. Możemy przyjąć (znów: kwestia oznaczeń), że $C$ jest znajomym zarówno $A$ , jak i $B$ , zaś $D$ jest znajomym $B$ .

Rozdzielamy parę $\{C,D\}$ i tworzymy dwie nowe pary: $\{A,C\}$ oraz $\{B,D\}$ . Wraz z pozostałymi parami $P_1,\ldots,P_{m-1}$ mamy w ten sposób $m + 1$ rozłącznych par znajomych. Uzyskana sprzeczność z maksymalnością $m$ dowodzi tezy zadania.