Задача
На бесконечной ленте выписаны в ряд числа. Первой идёт единица, а каждое следующее число получается из предыдущего прибавлением к нему наименьшей ненулевой цифры его десятичной записи. Сколько знаков в десятичной записи числа, стоящего в этом ряду на 9·10001000-м месте?
Решение
Поскольку каждое число ряда, начиная со второго, больше предыдущего, 9·10001000-е его число больше 9·10001000, то есть в нём как минимум 3001 цифра. Обозначим n-е число ряда через an, и пусть k – наименьший номер, при котором в числе ak 3002 цифры.
Рассмотрим числа от 0 до 103001 – 1, не имеющие единиц в десятичной записи. Дополнив каждое слева нулями до 3001 знака, мы получим все последовательности длины 3001 из цифр, отличных от единицы. Таких последовательностей 93001. Значит, и среди чисел a1, ..., ak–1 (все они не превосходят 103001 – 1) не более 93001 чисел, не имеющих единицы в десятичной записи .
Рассмотрим теперь процесс получения числа ak из a1. На каждом из k – 1 шагов прибавляется число от 1 до 9, причём количество шагов, на которых прибавляется не единица, не превосходит 93001. Значит, 103001 – 1 ≤ ak – a1 ≤ 9·93001 + 1·(k – 1 – 93001) = k – 1 + 8·93001, откуда
k ≥ 103001 8·93001 > 9·103000. Действительно, для этого достаточно доказать, что 8·93001 < 103000, то есть что (10/9)3000 > 72. Но согласно неравенству Бернулли (см. задачу 130899) (10/9)3000 > 1 + 3000/9 > 334.
Итак, число с 3002 знаками появляется в последовательности далее указанного в условии места.
Ответ
3001 знак.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь