|
|
 |
Условие
Взяли все 100-значные натуральные числа, в десятичной записи которых каждая цифра – какая-то из цифр 2, 3, 4, 5, 6, 7. Сколько из этих чисел делятся на $2^{100}$?
Решение
Докажем по индукции, что есть ровно $3n$ хороших $n$-значных чисел (кратных $2^n$ и составленных из указанных цифр). База ($n$ = 1) очевидна.
Шаг индукции. Если у хорошего $(n+1)$-значного числа стереть первую цифру, получится хорошее $n$-значное число (поскольку, стирая цифру $x$, мы вычитаем из числа, кратного $2^{n+1}$, число $x\cdot 10^n$, кратное $2^n$). С другой стороны, хорошее $n$-значное число имеет вид $y \cdot 2^n$. Приписывая к нему слева цифру $x$, мы добавляем число $(x \cdot 5^n)2^n$, и сумма будет делиться на $2^{n+1}$ тогда и только тогда, когда число $y + x \cdot 5^n$ чётно, то есть когда $x+y$ чётно. Видно, что для чётных $y$ в качестве $x$ подходят в точности чётные цифры 2, 4, 6, а для нечётного $у$ – в точности нечётные цифры 3, 5, 7. Значит, хороших $(n+1)$-значных чисел в 3 раза больше, чем хороших $n$-значных.
Ответ
$3^{100}$ чисел.
