kombinatoryka wakl: W pewnej grupie osób każde dwie osoby o tej samej liczbie znajomych nie mają wspólnych znajomych. Udowodnij, że w tej grupie istnieje osoba, która ma dokładnie jednego znajomego.

Blee: Zakładamy, że znajomość 'działa w obie strony' (nie ma możliwości, że A jest znajomym B, ale już B nie jest znajomym A). n −−− liczba osób k −−− maksymalna liczba znajomych przez jakąś z osób Niech n = 2 oraz k = 0 (czyli mamy dwóch obcych sobie ludzi) Natomiast w każdym innym przypadku (czyli gdy k > 0) Załóżmy, że mamy grupę 'n' ludzi. Wybieramy losowo jednego człeka (A). A zna dokładnie x osób, aby spełnione zostały warunki zadania I JEDNOCZEŚNIE nie spełniony był warunek 'istnieje osoba, która ma dokładnie jednego znajomego', to każdy z x znajomych osoby A musi mieć INNĄ liczbę znajomych (i większą od 1). Związku z tym, przynajmniej jeden z nich musi mieć co najmniej 'x+1' znajomych (niech to będzie osoba B). W takim razie znajomi B także muszą mieć inne (od siebie) liczby znajomych i skoro ta liczba ma być większa od 1 to znaczy, że przynajmniej jeden z nich musi mieć co najmniej 'x+2' znajomych. Itd. W końcu mamy sytuację w której ktoś musi mieć 'x+ ...ileś tam (nie będzie y) ..' znajomych, tyle że to x + y > n czyli musiałby mieć więcej znajomych niż liczy całą grupa (mało tego − chociaż jeden z jego znajomych musiałby mieć jeszcze więcej znajomych). sprzeczność