Разделы 
Дополнительно
Задача по математике - 3192
2019-05-27 
Докажите, что для любого $k > 1$ найдется степень 2 такая, что среди $k$ последних ее цифр не менее половины составляют девятки. (Например, $2^{12} = \cdots 96, 2^{53} = \cdots 992$.)
Решение:
От чего может появиться много девяток подряд в степенях двойки? - Если степень двойки «чуть» меньше числа, делящегося на большую степень десятки. Например, $2^{12} + 4$ делится на $100, 2^{53} + 8$ делится на 1000.
Попробуем найти сначала числа вида $2^n +1$, которые делятся на высокую степень пятерки. Затем домножим эти числа на соответствующую степень двойки и получим числа вида $2^k(2^n+1)$, делящиеся на высокую степень десятки. Раскрывая скобки и отбрасывая меньшее слагаемое, получим нужную степень двойки.
Лемма. При всех $k \geq 1$ число $2^{2 \cdot 5^{k-1}}+1$ делится на $5^k$.
Докажем это по индукции. База $(k=1)$ очевидна. Докажем шаг индукции: имеем
$2^{2 \cdot 5^{k-1}} + 1 = 4^{5^{k-1}} + 1$.
Пусть $a = 4^{5^{k-1}}$. По предположению индукции $a+1$ делится на $5k$. Тогда $4^{5^k} + 1 = a^5 + 1 = (a+1)(a^4 - a^3 + a^2 - a + 1)$. Поскольку $a+1$ делится на $5^k$, достаточно доказать, что второй сомножитель делится на 5. Действительно, a имеет вид $5m-1$, поэтому все слагаемые во втором сомножителе при делении на 5 дают остаток 1, а их сумма дает остаток нуль. Лемма доказана.
Итак, число $2^k(2^{2 \cdot 5^{k-1}} +1)$ оканчивается не меньше, чем $k$ нулями. Несложно убедиться, что при $k>1$ количество цифр числа $2^k$ не превосходит $k/2$. Значит, среди последних $k$ цифр числа $2^{2 \cdot 5^{k-1}+k}$ не более $k/2$ цифр могут отличаться от 9.
Докажите, что для любого $k > 1$ найдется степень 2 такая, что среди $k$ последних ее цифр не менее половины составляют девятки. (Например, $2^{12} = \cdots 96, 2^{53} = \cdots 992$.)
Решение:
От чего может появиться много девяток подряд в степенях двойки? - Если степень двойки «чуть» меньше числа, делящегося на большую степень десятки. Например, $2^{12} + 4$ делится на $100, 2^{53} + 8$ делится на 1000.
Попробуем найти сначала числа вида $2^n +1$, которые делятся на высокую степень пятерки. Затем домножим эти числа на соответствующую степень двойки и получим числа вида $2^k(2^n+1)$, делящиеся на высокую степень десятки. Раскрывая скобки и отбрасывая меньшее слагаемое, получим нужную степень двойки.
Лемма. При всех $k \geq 1$ число $2^{2 \cdot 5^{k-1}}+1$ делится на $5^k$.
Докажем это по индукции. База $(k=1)$ очевидна. Докажем шаг индукции: имеем
$2^{2 \cdot 5^{k-1}} + 1 = 4^{5^{k-1}} + 1$.
Пусть $a = 4^{5^{k-1}}$. По предположению индукции $a+1$ делится на $5k$. Тогда $4^{5^k} + 1 = a^5 + 1 = (a+1)(a^4 - a^3 + a^2 - a + 1)$. Поскольку $a+1$ делится на $5^k$, достаточно доказать, что второй сомножитель делится на 5. Действительно, a имеет вид $5m-1$, поэтому все слагаемые во втором сомножителе при делении на 5 дают остаток 1, а их сумма дает остаток нуль. Лемма доказана.
Итак, число $2^k(2^{2 \cdot 5^{k-1}} +1)$ оканчивается не меньше, чем $k$ нулями. Несложно убедиться, что при $k>1$ количество цифр числа $2^k$ не превосходит $k/2$. Значит, среди последних $k$ цифр числа $2^{2 \cdot 5^{k-1}+k}$ не более $k/2$ цифр могут отличаться от 9.
