Zasada szufladkowa Dirichleta

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Martino19
Użytkownik
Użytkownik
Posty: 13
Rejestracja: 20 maja 2018, o 23:22
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 7 razy

Zasada szufladkowa Dirichleta

Post autor: Martino19 »

Witam, mam prośbę czy mógłby mi ktoś wytłumaczyć (jak najprościej) jak rozwiązywać takie zadanie jak to:
Rozważamy dowolne 32 liczby całkowite nieujemne. Udowodnij, że istnieją wśród nich dwie, których suma lub różnica dzieli się przez 60.
Awatar użytkownika
kerajs
Użytkownik
Użytkownik
Posty: 8708
Rejestracja: 17 maja 2013, o 10:23
Płeć: Mężczyzna
Podziękował: 335 razy
Pomógł: 3431 razy

Re: Zasada szufladkowa Dirichleta

Post autor: kerajs »

Aby różnica dwóch liczb nie była podzielna przez 60, to powinny one mieć różne reszty przy dzieleniu przez 60. Wynika z tego że każda z 32 liczb powinna mieć inną resztę z dzielenia przez 60.
Mając 32 różne reszty naturalne z przedziału \(\displaystyle{ \left\langle 0,59\right\rangle}\) istnieje co najmniej jedna para o postaci k, 60-k i to suma liczb których one są resztą jest podzielna przez 60.
ODPOWIEDZ