|
|
 |
Условие
На экране суперкомпьютера напечатано число $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.
