Теория чисел на Высшей пробе

При решении задачи будем использовать свойство уменьшения первого разряда. Оно состоит в том, что при умножении двух цифр и получается либо однозначное число (цифра), либо двузначное, и в последнем случае первая цифра двузначного произведения меньше, чем минимальная из цифр .

Действительно, двузначные числа и больше, чем , так как . Тем самым на каждом шаге либо получается на цифру меньше (первый случай), либо число цифр сохраняется, но минимальная из всех цифр, написанных на доске, не увеличивается.

_________________________________________________________________________________________________________________________________________________________________________________

Будем доказывать утверждение задачи индукцией по числу При утверждение очевидно. Утверждение для следует из свойства уменьшения первого разряда, в силу которого через несколько шагов останется одна цифра.

_________________________________________________________________________________________________________________________________________________________________________________

Пусть утверждение доказано для . Пусть — минимальная из цифр, написанных на доске. Достаточно показать, что через несколько шагов либо число цифр уменьшится, либо минимальная цифра уменьшится: появится цифра меньше .

Предположим противное. Тогда число цифр не уменьшается и в каждый момент есть цифра , к которой очередной шаг задачи не применяется: каждый шаг не затрагивает хотя бы одну цифру . В противном случае, если осталась одна или две цифры , и к ней (соответственно, к ним обеим) применен шаг задачи, и при этом число цифр не уменьшается, то минимальная цифра уменьшится в силу свойства уменьшения первого разряда.

Вышесказанное эквивалентно тому, что все шаги задачи применяются к меньшему набору цифр: ко всем, кроме одной из цифр . А тогда по предположению индукции через несколько шагов на доске, кроме цифры , останется одна цифра. Это сводит шаг индукции к случаю двух цифр, для которого утверждение задачи доказано.