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.
Zasada szufladkowa
- yorgin
- Użytkownik
- Posty: 12762
- Rejestracja: 14 paź 2006, o 12:09
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 17 razy
- Pomógł: 3440 razy
Zasada szufladkowa
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.
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.