Parzysta liczba wspólnych znajomych

[Ogorek00]

W grupie jest parzyście wiele osób, każda osoba ma w niej parzystą liczbę znajomych (co więcej jeśli A zna B to B zna A i żadna osoba nie zna samej siebie). Pokaż, że istnieje para osób mająca parzystą liczbę wspólnych znajomych.

[Hydra147]

Załóżmy nie wprost, że każda para ma nieparzyście wiele wspólnych znajomych, rozważmy dowolną osobę i przez \(\displaystyle{ A}\) oznaczmy zbiór jej znajomych, a przez \(\displaystyle{ B}\) zbiór wszystkich pozostałych. Każda osoba w \(\displaystyle{ B}\) ma nieparzystą liczbę znajomych w \(\displaystyle{ A}\), ma zatem również nieparzystą liczbę osób w \(\displaystyle{ B}\) - ten ma jednak nieparzystą liczbę elementów i mamy sprzeczność z lematem o uściskach dłoni.