Udowodnić że 2 osoby mają tyle samo znajomych

[kordi1221]

Udowodnić, że w dowolnej grupie osób istnieją osoby o tej samej liczbie znajomych (w tej
grupie).

Jak to można udowodnić?

[yorgin]

Korzystając z zasady szufladkowej.

Pudełka etykietowane są ilością uścisków dłoni od \(\displaystyle{ 0}\) do \(\displaystyle{ n-1}\). Ale nie może być jednocześnie \(\displaystyle{ 0}\) uścisków jednej osoby i \(\displaystyle{ n-1}\) uścisków innej osoby, więc zostaje \(\displaystyle{ n-1}\) pudełek dla \(\displaystyle{ n}\) osób.

[kordi1221]

mógłby ktoś jaśniej i na innym przykładzie bo za bardzo nie rozumiem...

[yorgin]

Zacytuję z pewnej strony...

Pewna grupa osób wita się podając sobie ręce. Nikt nie wita się z samym sobą i żadna para osób nie wita się podwójnie. Czy muszą być dwie osoby, które witały taką samą liczbę osób?

Gdy jest \(\displaystyle{ n}\) osób, to każda z nich przywita\(\displaystyle{ 0}\) lub \(\displaystyle{ 1}\) lub 2 lub ... \(\displaystyle{ n-1}\) osób.
Utwórzmy więc \(\displaystyle{ n}\) szuflad z etykietami \(\displaystyle{ k=0,1,2,\ldots, n-1}\)i umieśćmy osobę w szufladzie o etykiecie \(\displaystyle{ k}\), jeśli witała się z dokładnie \(\displaystyle{ k}\) osobami.
Skoro jest \(\displaystyle{ n}\) osób i \(\displaystyle{ n}\) szuflad, to ...
niewiele z tego wynika
Ale... niewiele wynika tylko jeśli wszystkie szuflady będą zajęte, a tak jest w przypadku, gdy również dwa konkretne pudełka o etykietach \(\displaystyle{ 0}\) i \(\displaystyle{ n-1}\) są zajęte. Tyle, że nie jest to możliwe - nie może być osoby, która przywitała wszystkie pozostałe i równocześnie takiej, która nie przywitała nikogo.
A zatem \(\displaystyle{ n}\) osób zajęło co najwyżej \(\displaystyle{ n-1}\) szuflad, więc w jednej z nich są co najmniej dwie osoby - takie, które przywitały tę samą liczbę osób.