Matematyka.pl

Udowodnij, że w 17-osobowym towarzystwie, w którym każda osoba zna dokładnie 4 inne, istnieją dwie osoby, które się nie znają i nie mają wspólnych znajomych.

(relacja znajomości jest wzajemna, tzn. jeśli A zna B, to B też zna A)

Niech \(\displaystyle{ A_1}\) zna \(\displaystyle{ A_2,A_3,A_4,A_5}\) - wówczas żeby nie zachodziła teza, to każda z osób \(\displaystyle{ A_2,A_3,A_4,A_5}\) musi znać trzy spośród osób: \(\displaystyle{ A_6,\ldots,A_{17}}\) (gdyż \(\displaystyle{ A_2,A_3,A_4,A_5}\) "zostało" jeszcze 12 znajomych "do poznania", a tyle jest jeszcze "nie wykorzystanych" osób ).

Nie wprost: zatem wśród \(\displaystyle{ A_6,\ldots,A_{17}}\) każda para zna się wzajemnie lub ma wspólnych znajomych, niech \(\displaystyle{ A_6}\) zna \(\displaystyle{ A_7,A_8,A_9}\), wówczas liczba "wolnych" znajomych tej trójki wynosi 6, podczas gdy osób \(\displaystyle{ A_{10},\ldots,A_{17}}\) jest 8 - zatem pewna z osób \(\displaystyle{ A_{10},\ldots,A_{17}}\) nie zna osoby \(\displaystyle{ A_6}\) i nie ma z nią wspólnych znajomych, co należało dowieść.