Помогите решить задачу.

[macha2004]

Одной операцией к числу можно либо прибавить 9, либо стереть в нём в любом месте цифру 1. (Если единица стирается в начале числа, а за ней сразу идут нули, то эти нули тоже стираются.) Из любого ли натурального числа А при помощи таких операций можно получить число А + 1?

@темы: Теория чисел

Comments

[Adjirranirr]

Предположим, что исходное число имеет длину `n`. Число `k = 11...100...001` (`8` единиц, `100500^(2 n!)` нулей, единица) делится на `9`. Поэтому, прибавлениями `9` из числа `A` можно получить число `k + A = (k - 1) + (A + 1)`. Стерев `8` единиц, получим результат.

[All_ex]

`100500^(2 n!)` нулей, - красивое число... ...