Question

Докажите, что для каждого натурального числа n найдется число, в записи которого есть только нули и единицы, и которое делится нацело на n.
P.S. Если вдруг есть контрпример или утверждение верно не для всех n(то есть если есть доказательство, что условие задания неверно), достаточно привести его.

Answer 1

Рассмотрим последовательность из (n+1) числа.
1, 11, 111, ....., 111..111 (n+1 единиц) (*)
При делении любого натурального числа на n мы можем получить один из остатков:
0 ( деление без остатка),1,2,...,n-1

Рассмотрим n ячеек и пронумеруем их остатками при делении на n:
0,1,2....n-1
Тогда, согласно принципу Дирихле,
при раcпределении (n+1) чисел (*) по этим ячейкам найдется ячейка, в которой окажутся , по крайней мере два числа
А и B (A>B), т.к. число распределяемых чисел (n+1) больше чем ячеек n.

А это будет означать, что числа А и В будут иметь одинаковые остатки при делении на n.

Из чего следует, что их разность будет нацело делиться на n:

Пусть А=11...1 (k единиц) B=11..1 (m единиц)
A-B = 11..1-11...1=11...100..0 ( в полученной десятичной записи разности
(k-m) единиц, m нулей)

и эта разность будет делиться на n

Таким образом, мы доказали существование натурального числа , кратного n , в десятичной записи которого встречаются лишь нули и единицы.