XLVII OM - I - Zadanie 3

Zawody matematyczne:

XLVII OM, 1995-1996

Etap:

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.