w sali jest k+1 osób (k jest większe niż 1). Udowodnić, że wśród tych osób znajdują się takie dwie które mają tę samą liczbę znajomych na sali. (zakładamy, że relacja "znajomości" jest symetryczna).
Każda z osób może mieć od 1 do k znajomych, osób jest k+1, więc...
Musi być ktoś kto nie zna nikogo,
ale wtedy pozostaje grupa \(\displaystyle{ k}\) osób, w której maksymalna liczba znajomych to \(\displaystyle{ k-1}\), więc...