XLV OM - I - Zadanie 9

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.

Komentarze

Dodaj nową odpowiedź