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

Answer 2

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

Рассмотрим последовательность чисел 1, 11, 111, 1111, ... , где каждый следующий член получается приписыванием единицы к предыдущему. Если мы рассмотрим бесконечное множество таких чисел, а остатки от деления на n будут всегда меньше n (по принципу Дирихле), то обязательно найдутся два числа, которые имеют одинаковые остатки при делении на n.

Пусть, например, 11...1 (с n единицами) и 11...1 (с m единицами, где n < m). Тогда разность этих чисел будет иметь вид 11...100...0, где между первыми n и последними m единицами находятся нули. Это число делится на 10^n, которое, в свою очередь, делится на n (поскольку n - натуральное число).

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