Loading [MathJax]/jax/output/SVG/jax.js

Леонард Эйлер атындағы олимпиада,
2008-2009 оқу жылы, қорытынды кезеңнің 2-ші туры


Шексіз лентада тізбек бойынша сандар жазылған. Басында бір саны тұр, ал одан кейінгі сан, алдыңғы саннан сол санға оның ең кіші нөлдік емес цифрасын қосқаннан пайда болады. 910001000-шы орында тұрған сан қанша таңбалы сан? ( И. Богданов )
посмотреть в олимпиаде

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

Комментарии от администратора Комментарии от администратора №1.     Ответ. 3001.
Решение. Поскольку каждое число ряда, начиная со второго, больше предыдущего хотя бы на единицу, 910001000-ое его число больше 910001000, то есть в нём как минимум 3001 цифра. Обозначим n-ое число ряда через an, и пусть k — наименьший номер такой, что в числе ak 3002 цифры. Если мы докажем, что k>910001000, то получим, что в 910001000-ом числе ряда не более 3001 цифры, то есть в нем ровно 3001 цифра.
Рассмотрим числа от 0 до 1030011, не имеющие единиц в десятичной записи. Дополнив каждое слева нулями до 3001 знака, мы получим все последовательности длины 3001 из цифр, отличных от единицы. Таких последовательностей 93001. Значит, и среди чисел a1,,ak1 не более 93001 чисел, не имеющих единицы в десятичной записи (так как все они не превосходят 1030011). Рассмотрим теперь процесс получения числа ak из a1. На каждом из k1 шагов прибавляется число от 1 до 9, причём количество шагов, на которых прибавляется не единица, не превосходит 93001. Значит, 1030011aka1993001+1(k193001)=k1+893001, откуда k103001893001. Осталось показать, что 103001893001>9103000. Для этого достаточно доказать, что 93002<103000. Заметим, что 97=4782969<5106, откуда 928<541024<1027и956<1054. Поэтому 93002=95692946<1054102946=103000.