Покажем, как за 118 ходов получить число 1049. Сначала увеличиваем число на 9. Потом 13 раз повторяем одну и ту же операцию: 8 раз увеличиваем число на 9 и один раз увеличиваем число на 8 (одна операция содержит 9 ходов, а 13*9+1=118). В результате 10 первых ходов получим числа 9, 18, 27, 36, 45, 54, 63, 72, 81, 89. Поскольку к началу второй операции последняя цифра снова равна 9, последние цифры будут повторяться и среди них не будет цифры 0, то есть, ни на каком шаге полученное число не будет делиться на 10. За одну операцию число увеличится на 8*9+1*8=80. Тогда результат будет равен 9+13*80=1049. Заметим, что всего мы 13 раз прибавили 8 и 118-13=105 раз прибавили 9.
Предположим, что мы смогли получить число, большее 1049. Но тогда мы должны хотя бы 106 раз из 118 прибавить цифру 9 и не более 12 раз прибавить другие цифры. Разобьем последние 117 шагов на 13 групп по 9, тогда хотя бы в одной группе на всех шагах будут прибавляться девятки. Это означает, что на каком-то этапе мы прибавляем девятку 9 раз подряд, при этом число, имеющееся перед первым шагом, не делится на 10. Пусть последняя цифра этого числа равна x, тогда после прибавления x девяток мы получим число, делящееся на 10 (после каждого прибавления девятки последняя цифра числа уменьшается на 1). Поскольку x не превосходит 9, число, кратное 10 будет неизбежно получено, что противоречит условию. Значит, за 118 ходов мы не можем прибавить более 105 девяток и получить число, большее 105*9+13*8=1049.
