Obóz naukowy OMG»Zadanie 2
o zadaniu...
- Zadanie pochodzi z artykułu Obóz naukowy OMG
- Publikacja w Delcie: grudzień 2011
- Publikacja elektroniczna: 01-12-2011
Na przyjęciu spotkało się
osób. Okazało się, że żadnych
dwóch znajomych nie ma wspólnego znajomego. Ponadto każdych
dwóch nieznajomych ma dokładnie dwóch wspólnych znajomych.
Udowodnij, że wszystkie osoby obecne na tym przyjęciu mają taką samą liczbę
znajomych.
będzie dowolną osobą uczestniczącą w przyjęciu
i niech
będzie zbiorem jej znajomych, a
zbiorem osób, których nie zna.
osoby
i
nie znają się między sobą
(ponieważ
jest ich wspólnym znajomym). Stąd dowolne dwie
osoby z
mają dokładnie jednego wspólnego znajomego w zbiorze
(dla każdego
) zna dokładnie dwie osoby ze zbioru
ponieważ ma z
dwóch wspólnych znajomych. Stąd
żadne trzy osoby z
nie mają wspólnego znajomego w zbiorze
ma dokładnie
znajomych – jest
to
oraz
osób ze zbioru
odpowiadających parom
dla
ma tyle samo znajomych, co każdy jego
znajomy. Z dowolności wyboru
oraz faktu, że dowolnych dwóch
nieznajomych ma wspólnego znajomego, otrzymujemy tezę.