XLVII OM - I - Zadanie 3

W pewnej grupie $ kn $ osób każda osoba zna więcej niz $ (k - 1)n $ innych ($ k $, $ n $ są liczbami naturalnymi). Wykazać, że można z tej grupy wybrać $ k + 1 $ osób, z których każde dwie sie znają.

Uwaga: Jeżeli osoba $ A $ zna osobę $ B $, to osoba $ B $ zna osobę $ A $.

Rozwiązanie

Grupkę osób, z których każda zna każdą, będziemy nazywać {\it kliką}. Niech $ m $ będzie największą liczbą naturalną, dla której w rozważanej grupie $ kn $ osób istnieje $ m $-osobowa klika. Wykażemy, że $ m>k $. Stąd już wyniknie dowodzona teza, bowiem dowolny ($ k+1 $)-elementowy podzbiór takiej maksymalnej $ m $-osobowej kliki jest wówczas ($ k+1 $)-osobową kliką.

Niech więc $ \{p_1,\ldots,p_m\} $ będzie $ m $-osobową kliką. Oznaczmy przez $ N_i $ zbiór wszystkich osób nieznajomych dla $ p_i \ (i = 1,\ldots,m) $, a przez $ n_i $ liczbę osób w zbiorze $ N_i $. Każda osoba $ p_i $ zna więcej niż $ kn-n $ innych, więc grono jej nieznajomych liczy mniej niż $ n-1 $ osób:

\[<br />
n_i < n -1 \textrm{ dla } i = 1,\ldots,m.<br />
\]

Poza kliką $ \{p_1,\ldots,p_m\} $ znajduje się $ kn-m $ osób; oznaczmy ich zbiór przez $ Q $.

Weźmy dowolną osobę $ q $ ze zbioru $ Q $. Gdyby była ona znajomą wszystkich osób $ p_1,p_2, \ldots, p_m $, moglibyśmy ją do nich dołączyć, a powstały zbiór $ \{p_1,p_2, \ldots, p_m, q \} $ byłby ($ m+1 $)-osobową kliką. To się jednak kłóci z określeniem $ m $ jako największej możliwej liczby osób w klice.

Stąd wniosek, że każda osoba ze zbioru $ Q $ jest nieznajoma dla kogoś z kliki $ \{p_1,\ldots, p_m \} $, a więc należy do co najmniej jednego zbioru $ N_i $. Wobec tego liczba osób w zbiorze $ Q $ (równa $ kn-m $) nie przekracza łącznej liczby osób w zbiorach $ N_1, \ldots , N_m $. Zachodzi zatem nierówność

\[<br />
kn-m \leq n_1 + \ldots +n_m < (n-1)+ \ldots + (n-1) = m(n-1);<br />
\]

po redukcji: $ k<m $. Jak stwierdziliśmy na wstępie, ta nierówność wystarcza do zakończenia dowodu.

Komentarze

Dodaj nową odpowiedź