Задача 67401
|
|
 |
Условие
Взяли все $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$-значных.
