Номер 47.37, страница 367 - гдз по алгебре 10 класс учебник Мерзляк, Номировский

47.37. Докажите, что для любого натурального числа $n$ найдётся натуральное число, кратное $n$, в десятичной записи которого используются только цифры 1 и 0.

Для доказательства воспользуемся принципом Дирихле. Рассмотрим последовательность, состоящую из $n$ натуральных чисел, десятичная запись каждого из которых состоит только из цифр 1:

$a_1 = 1$

$a_2 = 11$

$a_3 = 111$

...

$a_n = \underbrace{11\dots1}_{n \text{ раз}}$

Теперь рассмотрим остатки от деления этих $n$ чисел на данное натуральное число $n$. Пусть $r_k$ — это остаток от деления числа $a_k$ на $n$, то есть $r_k = a_k \pmod n$. Мы получим $n$ остатков: $r_1, r_2, \dots, r_n$.

При делении на $n$ существует ровно $n$ возможных остатков: $0, 1, 2, \dots, n-1$.

Далее возможны два случая:

Случай 1: Один из остатков равен нулю.

Пусть для некоторого $k$ (где $1 \le k \le n$) остаток $r_k = 0$. Это означает, что число $a_k$ делится на $n$ нацело. Число $a_k$ состоит только из цифр 1, что удовлетворяет условию (в его записи используются только цифры 1 и 0). Следовательно, в этом случае число $a_k$ является искомым.

Случай 2: Ни один из остатков не равен нулю.

Если ни один из остатков $r_1, r_2, \dots, r_n$ не равен 0, то все эти $n$ остатков принимают значения из множества $\{1, 2, \dots, n-1\}$. В этом множестве всего $n-1$ различный элемент. Поскольку у нас есть $n$ остатков, а возможных значений для них только $n-1$, то по принципу Дирихле как минимум два остатка должны быть одинаковыми. Пусть $r_i = r_j$ для некоторых $i$ и $j$ таких, что $1 \le i < j \le n$.

Равенство остатков $r_i = r_j$ означает, что $a_j \equiv a_i \pmod n$. Отсюда следует, что их разность $(a_j - a_i)$ кратна $n$. Рассмотрим это число $M = a_j - a_i$.

$M = \underbrace{11\dots1}_{j \text{ раз}} - \underbrace{11\dots1}_{i \text{ раз}} = \underbrace{11\dots1}_{j-i \text{ раз}}\underbrace{00\dots0}_{i \text{ раз}}$

Например, если $n=7$, $j=6$, $i=3$, то $a_6=111111$, $a_3=111$. $a_6 \equiv 5 \pmod 7$, $a_3 \equiv 6 \pmod 7$. Это плохой пример. Возьмем $n=3$. $a_1=1 \equiv 1 \pmod 3$, $a_2=11 \equiv 2 \pmod 3$, $a_3=111 \equiv 0 \pmod 3$. Это случай 1. Возьмем $n=4$. $a_1=1 \equiv 1 \pmod 4$, $a_2=11 \equiv 3 \pmod 4$, $a_3=111 \equiv 3 \pmod 4$. Здесь $i=2, j=3$. $M = a_3 - a_2 = 111-11 = 100$. Число 100 делится на 4, и в его записи только 1 и 0.

Число $M$ является натуральным, так как $j>i$. В его десятичной записи используются только цифры 1 и 0. Поскольку $M$ делится на $n$, оно является искомым числом.

Таким образом, в любом из двух возможных случаев мы находим натуральное число, удовлетворяющее условиям задачи. Утверждение доказано.

Ответ: Для любого натурального числа $n$ доказано существование натурального числа, кратного $n$, в десятичной записи которого используются только цифры 1 и 0.