Докажите, что для каждого натурального числа n найдется число, в записи которого есть только нули и единицы, и которое делится нацело на n.

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

Рассмотрим последовательность из (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, в десятичной записи которого встречаются лишь нули и единицы.