Matematyka.pl

Wykaż, że dla dowolnej liczby \(\displaystyle{ n}\) istnieje liczba zapisana tylko przy pomocy zer i jedynek, która dzieli się przez \(\displaystyle{ n}\).

Warunki zadania spełnia liczba \(\displaystyle{ 0}\), ale raczej nie o to chodziło.

Jest to klasyczne zadanie na zasadę szufladkową Dirichleta. Rozważ liczby postaci \(\displaystyle{ 11\ldots 1}\) modulo \(\displaystyle{ n}\). Możliwych reszt jest skończenie wiele.

Czy JakimPL, chodzi o to że wśród n+1 liczb postaci \(\displaystyle{ 1111...111}\) co najmniej dwie dają ta samą resztę mod \(\displaystyle{ n}\) i ich różnicą dzieli się przez \(\displaystyle{ n}\)??? A taka różnica będzie się składać z samych zer i jedynek.

Tak, dokładnie o to chodziło .

Rozważmy \(\displaystyle{ n+1}\) liczb naturalnych postaci \(\displaystyle{ 1, 11, 111, \ldots, \underbrace{11\ldots 1}_{n+1}}\). Na mocy zasady szufladkowej Dirichleta dokładnie dwie z nich dają taką samą resztę z dzielenia przez \(\displaystyle{ n}\). Oznaczmy te liczby przez \(\displaystyle{ a_{i}=\underbrace{11\ldots 1}_{i}}\) oraz \(\displaystyle{ a_{j}=\underbrace{11\ldots 1}_{j}}\), przy czym \(\displaystyle{ n+1\geqslant i>j}\).Gdy dwie liczby dają taką samą resztę z dzielenia przez \(\displaystyle{ n}\), to wówczas ich różnica jest podzielna przez \(\displaystyle{ n}\). Oznacza to, że przez \(\displaystyle{ n}\) podzielna jest liczba \(\displaystyle{ a_{i}-a_{j}=\underbrace{11\ldots 1}_{i}-\underbrace{11\ldots 1}_{j}=\underbrace{11\ldots 1}_{i-j}\underbrace{00\ldots 0}_{j}}\). Liczba ta zapisana jest jedynie przy pomocy zer i jedynek oraz jest podzielna przez \(\displaystyle{ n}\), a to kończy dowód.