zasada szufladkowa Dirichleta

[pg2464]

Witam, proszę o pomoc przy rozwiązaniu poniższego zadania

Udowodnij, że wśród dowolnych \(\displaystyle{ 52}\) liczb naturalnych są dwie, których suma lub różnica dzieli się przez \(\displaystyle{ 100}\).

[kerajs]

Ile jest możliwych reszt z dzielenia liczby naturalnej przez \(\displaystyle{ 100}\)? Dokładnie \(\displaystyle{ 100}\), od \(\displaystyle{ 0}\) do \(\displaystyle{ 99}\).
Jeśli reszty są identyczne to różnica liczb naturalnych je posiadająca jest podzielna przez \(\displaystyle{ 100}\). Ile jest niepowtarzających się reszt z których suma nie jest podzielna przez \(\displaystyle{ 100}\)? Tylko \(\displaystyle{ 50}\), bo dla wybranej reszty \(\displaystyle{ x}\), nie można wybrać reszty \(\displaystyle{ 100-x}\). Stąd teza jest prawdziwa.

[Mruczek]

Ile jest niepowtarzających się reszt z których suma nie jest podzielna przez \(\displaystyle{ 100}\)?

Chyba miało być: "których suma jest podzielna przez".
Z tym zdaniem jest coś nie tak.

Tylko \(\displaystyle{ 50}\)

Raczej \(\displaystyle{ 51}\). Nie wiem co miałeś na myśli - patrz moje rozwiązanie poniżej.

Rozwiązanie:    

Jeżeli pewne dwie z tych \(\displaystyle{ 52}\) liczb dają taką samą resztę z dzielenia przez \(\displaystyle{ 100}\) to bierzemy różnicę tych liczb, w przeciwnym przypadku każda z liczb ma inną resztę. Wtedy parujemy możliwe reszty (w pary o sumie podzielnej przez \(\displaystyle{ 100}\)): \(\displaystyle{ (i, 100 - i)}\) dla \(\displaystyle{ 1\le i \le 49}\), reszty \(\displaystyle{ 0}\) i \(\displaystyle{ 50}\) pozostają niesparowane. Mamy łącznie \(\displaystyle{ 51}\) grup (par lub pojedynczych) reszt, ale \(\displaystyle{ 52}\) liczby, więc pewna para musi być wykorzystana w całości - bierzemy sumę tych dwóch liczb, których reszty występują w parze.

[kerajs]

Z tym zdaniem jest coś nie tak.

To akurat jest w porządku. Błąd popełniłem gdy przegapiłem że reszty \(\displaystyle{ 0}\) i \(\displaystyle{ 50}\) ( które Ty nazywasz niesparowanymi) nie tworzą układu \(\displaystyle{ x, 100-x}\) . Dlatego możliwych do wyboru jest nie \(\displaystyle{ 50}\), a \(\displaystyle{ 51}\) reszt których suma lub różnica dwóch z nich nie jest podzielna przez \(\displaystyle{ 100}\).