Seminaria „Poznajemy OMG”»Zadanie 1
o zadaniu...
- Zadanie pochodzi z artykułu Seminaria „Poznajemy OMG”
- Publikacja w Delcie: listopad 2012
- Publikacja elektroniczna: 01-11-2012
Udowodnij, że w dowolnej grupie osób zawsze znajdą się dwie takie, które
mają tyle samo znajomych (przyjmujemy, że jeśli osoba
zna osobę
to także osoba
zna osobę
).
liczbę osób w rozważanej grupie. Wówczas każda
z nich może znać
lub wszystkich
spośród
pozostałych; łącznie jest
możliwości – tyle, ile osób. Gdyby
każdy miał inną liczbę znajomych, to w rozważanym gronie byłaby
osoba
która nie zna nikogo, oraz osoba
która zna
wszystkich. To prowadzi do sprzeczności, bo czy wtedy
i
się
znają, czy nie? Wobec tego nie jest możliwe, by każdy miał inną liczbę
znajomych.