Zasada szufladkowa

[max12333]

Proszę o pomoc z zadaniem:
Do pokoju wchodzi \(\displaystyle{ n}\) osób, a następnie się witają. Wykazać, że przynajmniej \(\displaystyle{ 2}\) osoby muszą przywitać się tą samą ilość razy.

Nie mam pomysłu w jaki sposób rozwiązać to zadanie. Próbowałem stworzyć \(\displaystyle{ n}\) szufladek i ponumerować je liczbami od \(\displaystyle{ 0}\) do \(\displaystyle{ n-1}\), które oznaczałyby ilość "przywitań" danej osoby. Niestety to nie przyniosło żadnego rezultatu, bo mamy \(\displaystyle{ n}\) szufladek i \(\displaystyle{ n}\) osób.

Z góry wielkie dzięki za pomoc.

[yorgin]

Do szufladki lądują osoby witające się \(\displaystyle{ k}\) razy, gdzie \(\displaystyle{ k\in\{0,\ldots,n-1\}}\)

Ale zauważ, że jeśli zajęta jest szufladka \(\displaystyle{ n-1}\), to nie może być zajęta szuflada \(\displaystyle{ 0}\), i odwrotnie. Czyli jedna wyklucza drugą. Dostajesz więc mniej szufladek niż osób.