Задача 67192

Темы:    [ Теория алгоритмов (прочее) ] [ Теория чисел. Делимость (прочее) ]

Сложность: 5 Классы: 9,10,11

Условие

Автор: Евдокимов М.А.

На экране суперкомпьютера напечатано число $11\ldots 1$ ($900$ единиц). Каждую секунду суперкомпьютер заменяет его по следующему правилу. Число записывается в виде $\overline{AB}$, где $B$ состоит из двух его последних цифр, и заменяется на $2\cdot A + 8\cdot B$ (если $B$ начинается на нуль, то он при вычислении опускается). Например, $305$ заменяется на $2\cdot 3 + 8 \cdot 5 = 46$. Если на экране остаётся число, меньшее $100$, то процесс останавливается. Правда ли, что он остановится?

Решение

Условие можно перефразировать так: если число на экране имеет вид $100A + B$, где $0\leqslant B < 100$, то оно заменяется на число $2A + 8B$. Поэтому оно уменьшается на $(100A + B ) - (2A + 8B) = 98 A - 7B = 7 (14 A - B)$. Эта величина обязательно положительна при $A > 7$, так что все числа, начиная с 800, обязательно уменьшаются. Естественный вопрос — а может ли что-нибудь помешать числу уменьшиться дальше? Или можем ли мы выяснить, до какого числа, меньшего 800, «досчитает» суперкомпьютер? Во-первых, из записи выше видно, что разница между числом и его образом обязательно делится на 7. Так что остаток от деления на 7 сохраняется. А поскольку на 7 делится $1001=7\cdot 11\cdot 13$, то делится и $111111=111\cdot1001$, значит, и число из $900=6\cdot 150$ единиц. Значит, все числа, которые будут получаться, тоже делятся на $7$, а также и на 14, потому что $2A+8B$ — это всегда число чётное.

Но этого мало. А не сохраняется ли (или не изменяется ли предсказуемым образом) делимость на ещё какое-нибудь простое число $p$?

Если на $p$ делится $100A+B$, то делится и $8(100A+B)=800A+8B$ (а если не делится, то остаток умножается ровно на $8$). Разница между этим числом и $2A+8B$ составляет $(800-2)A=798A$, так что если $p$ — делитель $798$, то остаток от деления на $p$ умножится на $8$. Учтём, что $798=7\cdot114=7\cdot2\cdot3\cdot19$; это даёт нам два новых простых числа, $3$ и $19$.

Посмотрим, какой остаток даёт исходное число при делении на $3$ и на $19$. Оно делится на 3, потому что $900$ делится на $3$. Наконец, то, что $10^{18}-1$ делится на $19$, следует из Малой теоремы Ферма, но можно проверить и просто «делением в столбик». А значит, делится на 19 и число из $900=18\cdot50$ единиц. Поэтому все итерации, начиная со второй, будут делиться на $798$. И значит, итоговое (ненулевое!) число никогда не станет меньше $100$.

Комментарий. Если бы нам не «повезло» с выбором исходного числа — можно было бы отследить изменение остатков от деления на 3, 7 и 19 (поскольку они на каждом шаге умножаются на 8) и понять, есть ли среди получающихся вариантов числа, меньшие 100.

Ответ

нет, не остановится.

Источники и прецеденты использования

олимпиада
Название	Московская математическая олимпиада
год
Номер	86
Год	2023
класс
Класс	10
задача
Номер	4