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)
[Kombinatoryka] Graf o 17 wierzchołkach - dowód.
Regulamin forum
Wszystkie tematy znajdujące się w tym dziale powinny być tagowane tj. posiadać przedrostek postaci [Nierówności], [Planimetria], itp.. Temat może posiadać wiele różnych tagów. Nazwa tematu nie może składać się z samych tagów.
Wszystkie tematy znajdujące się w tym dziale powinny być tagowane tj. posiadać przedrostek postaci [Nierówności], [Planimetria], itp.. Temat może posiadać wiele różnych tagów. Nazwa tematu nie może składać się z samych tagów.
-
Sylwek
- Użytkownik
- Posty: 2692
- Rejestracja: 21 maja 2007, o 14:24
- Płeć: Mężczyzna
- Lokalizacja: Katowice
- Podziękował: 160 razy
- Pomógł: 664 razy
[Kombinatoryka] Graf o 17 wierzchołkach - dowód.
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ść.
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ść.