Na przyjęciu

[mol_ksiazkowy]

Na przyjęciu było \(\displaystyle{ 2n}\) osób i każdy z nich miał parzystą ilość znajomych.
Udowodnić, że istnieją osoby A i B, które mają parzystą ilość wspólnych znajomych na tym przyjęciu.
Uwagi: Jeśli jakaś osoba A zna B, to także B zna A

[Mruczek]

Znane zadanie. Przenosimy je na terminologię grafową.

Dyskusja:

Kod: Zaznacz cały

https://artofproblemsolving.com/community/c6h68109

.

Założenie o tym, że wszystkie wierzchołki mają parzysty stopień nie jest potrzebne - ten fakt zachodzi w dowolnych grafach o parzystej liczbie wierzchołków.

Przy założeniu o wierzchołkach parzystego stopnia prawdziwy jest nawet mocniejszy fakt:
dla każdego wierzchołka \(\displaystyle{ A}\) istnieje wierzchołek \(\displaystyle{ B}\) taki, że mają one parzystą liczbę wspólnych znajomych.
Pokażę to:

Weźmy dowolny wierzchołek \(\displaystyle{ A}\). Niech \(\displaystyle{ X}\) będzie zbiorem jego sąsiadów, a \(\displaystyle{ Y}\) zbiorem wierzchołków, z którymi nie jest połączony. \(\displaystyle{ X}\) ma parzystą wielkość, bo \(\displaystyle{ A}\) ma parzysty stopień. Cały graf ma parzystą liczbę wierzchołków, więc \(\displaystyle{ Y}\) ma nieparzystą wielkość. Jeżeli któryś wierzchołek w \(\displaystyle{ X}\) ma parzystą liczbę sąsiadów w \(\displaystyle{ X}\) to jest on szukanym wierzchołkiem, bo on i \(\displaystyle{ A}\) mają parzystą liczbę wspólnych sąsiadów. Jeżeli nie, to każdy wierzchołek z \(\displaystyle{ X}\) ma nieparzystą liczbę sąsiadów w \(\displaystyle{ X}\), ale jest sąsiadem \(\displaystyle{ A}\) oraz ma parzysty stopień, więc ma parzystą liczbę sąsiadów w \(\displaystyle{ Y}\). Tak więc łączna liczba krawędzi między zbiorami \(\displaystyle{ X}\) i \(\displaystyle{ Y}\) jest parzysta.
Jeżeli jakiś wierzchołek z \(\displaystyle{ Y}\) ma parzystą liczbę sąsiadów w \(\displaystyle{ X}\) to koniec, bo ma parzystą liczbę wspólnych sąsiadów z \(\displaystyle{ A}\). Wpp. każdy wierzchołek z \(\displaystyle{ Y}\) ma nieparzystą liczbę sąsiadów w \(\displaystyle{ X}\), ale \(\displaystyle{ Y}\) ma nieparzystą wielkość, więc liczba krawędzi między zbiorami \(\displaystyle{ X}\) i \(\displaystyle{ Y}\) jest nieparzysta (bo suma nieparzystej liczby liczb nieparzystych jest nieparzysta) - sprzeczność, cnd.

[kerajs]

A co z grafem cyklicznym ?
Czy zerowa, co prawda także parzysta, ilość wspólnych znajomych nie kłóci się ze sformułowaniem: mają (..) wspólnych znajomych ? Przecież wtedy nie mają wspólnych znajomych.

[Mruczek]

Wg mnie w moim rozwiązaniu nie ma znaczenia czy graf ma cykle czy nie.
Parzysta liczba wspólnych znajomych może być zerowa - na przykład jeżeli nikt w grupie się nie zna to taki graf spełnia założenia zadania i dowolna para osób jest szukaną parą o wspólnej liczbie znajomych równej zero.