МОШ 2023, 10 класс, задача 4
На экране написано число из единиц. Каждую минуту суперкомпьютер заменяет его по следующему правилу. Число записывается в виде , где состоит из двух его последних цифр, и заменяется на (если начинается на нуль, то он при вычислении опускается). Например, заменяется на . Если на экране остаётся число, меньшее , то процесс останавливается. Правда ли, что он остановится?
(М. Евдокимов)
Ответ
Ответ. Нет, не остановится.
Решение. Условие можно перефразировать как то, что если число на экране имеет вид , где , то оно заменяется на число . Поэтому оно уменьшается на
Эта величина обязательно положительна при , так что все числа, начиная с , обязательно уменьшаются. Естественный вопрос -- а может ли что-нибудь помешать числу уменьшиться дальше? Или можем ли мы выяснить, до какого числа, меньшего , «досчитает» суперкомпьютер?
Во-первых, из записи выше видно, что разница между числом и его образом обязательно делится на . Так что остаток от деления на сохраняется. А поскольку на делится , то делится и , и значит, и число из единиц. Значит, все числа, которые будут получаться, тоже делятся на -- и на , потому что это всегда число чётное.
Но этого мало. А не сохраняется ли (или не изменяется ли предсказуемым образом) делимость на ещё какое-нибудь простое число ? Если на делится , то делится и (а если не делится, то остаток умножается ровно на ). Разница между этим числом и составляет , так что если -- это делитель , то остаток от деления на умножится на . ; это даёт нам два новых простых числа, и .
Посмотрим, какой остаток даёт исходное число при делении на и на . Оно делится на , потому что делится на . Наконец, то, что делится на -- следует из Малой Теоремы Ферма, но можно проверить и просто «делением в столбик». А значит, делится на и число из единиц. Поэтому все итерации, начиная со второй, будут делиться на . И значит, итоговое (ненулевое!) число никогда не станет меньше .
Комментарий. Если бы нам не «повезло» с выбором исходного числа -- можно было бы «отследить» изменение остатков от деления на , и (поскольку они на каждом шаге умножаются на ), и понять, есть ли среди получающихся вариантов числа, меньшие .