Задача из журнала «Квант» (2001 год, 1 выпуск) M1739

Условие

Пусть $A$ – произвольная четная цифра, $B$ –произвольная нечетная цифра. Докажите, что существует натуральное число, делящееся на $2^{2000},$ каждая цифра которого – либо $A,$ либо $B.$

Решение

Укажем способ составления из цифр $A$ и $B$ числа, делящегося на $2^n$ для любого натурального $n.$ Обозначим такое число $G_n.$ При $n = 1$ полагаем $G_n=G_1= A.$ Пусть построено число $G_k$ при $n=k \geqslant 1.$ Воспользуемся им при построении следующего числа $G_{k+1},$ делящегося на $2^{k+1}$.

Если $G_k$ делится на $2^{k+1},$ то полагаем $G_{k+1}=G_k,$ в противном случае построим вспомогательное число $F_k$ , обладающее следующими свойствами: число $F_k$ составлено из цифр $A$ и $B$, делится на $2^k$ и имеет в своей десятичной записи ровно $k$ цифр.

Если $G_k$ имеет в своей записи ровно $k$ цифр, то полагаем $F_k=G_k$.

Если в записи $G_k$ более $k$ цифр, положим $F_k$ равным числу, получающемуся из $G_k$ отбрасыванием старших цифр, начиная с $(k + 1)$-й. По признаку делимости на $2^k,$ полученное из $G_k$ после такой операции число $F_k$ будет также делиться на $2^k$.

Если в записи $G_k$ менее $k$ цифр, припишем к числу $G_k$ слева его же несколько раз таким образом, чтобы в результате получилось число, в записи которого не менее $k$ цифр. Это число делится на $G_k$ и, следовательно, на $2^k.$ Если из него отбросить все старшие цифры, начиная с $(k + 1)$-й, то в результате получим число $F_k,$ которое, по признаку делимости на $2^k,$ также делится на $2^k.$

Если число $F_k$ делится на $2^{k+1},$ то полагаем $G_{k+1}=F_k,$ в противном случае полагаем $G_{k+1}=\overline{B F_k},$ приписав к числу $F_k$ число $B$ слева. Положив $F_k=2^k p,$ где $p$ – некоторое нечетное число, получаем $G_{k+1}=10^k B+2^k p=2^k (5^k B + p).$ В скобках стоит четное число, поэтому $G_{k+1}$ делится на $2^{k+1}.$

И.Акулич, А.Жуков

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *