Олимпиада имени Леонарда Эйлера2008-2009 учебный год, II тур заключительного этапа

На бесконечной ленте выписаны в ряд числа. Первой идёт единица, а каждое следующее число получается из предыдущего прибавлением к нему наименьшей ненулевой цифры его десятичной записи. Сколько знаков в десятичной записи числа, стоящего в этом ряду на $9 \cdot 1000^{1000}$-ом месте? ( И. Богданов )

Комментарий/решение

Комментарии от администратора Комментарии от администратора №1.     Ответ. 3001.
Решение. Поскольку каждое число ряда, начиная со второго, больше предыдущего хотя бы на единицу, $9 \cdot 1000^{1000}$-ое его число больше $9 \cdot 1000^{1000}$, то есть в нём как минимум 3001 цифра. Обозначим $n$-ое число ряда через $a_n$, и пусть $k$ — наименьший номер такой, что в числе $a_k$ 3002 цифры. Если мы докажем, что $k > 9 \cdot 1000^{1000}$, то получим, что в $9 \cdot 1000^{1000}$-ом числе ряда не более 3001 цифры, то есть в нем ровно 3001 цифра.
Рассмотрим числа от 0 до $10^{3001} - 1$, не имеющие единиц в десятичной записи. Дополнив каждое слева нулями до 3001 знака, мы получим все последовательности длины 3001 из цифр, отличных от единицы. Таких последовательностей $9^{3001}$. Значит, и среди чисел $a_1, \dots, a_{k-1}$ не более $9^{3001}$ чисел, не имеющих единицы в десятичной записи (так как все они не превосходят $10^{3001}- 1$). Рассмотрим теперь процесс получения числа $a_k$ из $a_1$. На каждом из $k - 1$ шагов прибавляется число от 1 до 9, причём количество шагов, на которых прибавляется не единица, не превосходит $9^{3001}$. Значит, $$10^{3001} - 1 \leq a_k - a_1 \leq 9 \cdot 9^{3001}+1 \cdot (k - 1 - 9^{3001}) = k - 1+8 \cdot 9^{3001},$$ откуда $k \geq 10^{3001} - 8 \cdot 9^{3001}$. Осталось показать, что $10^{3001} - 8 \cdot 9^{3001} > 9 \cdot 10^{3000}$. Для этого достаточно доказать, что $9^{3002} < 10^{3000}$. Заметим, что $9^{7} = 4782969 < 5 \cdot 10^6$, откуда $9^{28} < 5^4 \cdot 10^{24} < 10^{27} и 9^{56} < 10^{54}$. Поэтому $9^{3002} = 9^{56} \cdot 9^{2946} < 10^{54} \cdot 10^{2946} = 10^{3000}$.