Задача М140‍‍

а) Вместо того чтобы получить с помощью операций А, Б, В из числа 4 число 1972, мы попробуем получить из числа 1972 число 4 с помощью обратных операций:

1. вычёркивание цифры 4 в конце;
2. вычёркивание цифры 0 в конце;
3. умножение числа на 2.

При этом мы будем каждый раз, как только это возможно, применять операцию А′ или Б′, чтобы по возможности на каждом шаге уменьшать наше число. Получим: $$ 1972\to3944\to394\to39\to78\to156\to312\to624\to62\to124\to12\to24\to2\to4. $$

Ясно, что прочитав эту последовательность от конца к началу, мы получим нужный результат. (Операция Б′ здесь не используется.)

б) Докажем, что если с каждым числом $N$‍‍ поступать так же, как мы поступали с числом 1972 (применять операцию А′ или Б′, а если это не возможно — В′), то через несколько шагов мы придёмм к числу 4.

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

Итак, убедимся, что каждое число за несколько операций А′, Б′, В′ можно уменьшить (или прийти из него к  4; этот последний случай мы дальше особо не оговариваем).

Если последняя цифра числа $0$‍‍ или $4$‍,‍ то после применения А′ или Б′ оно уменьшается по крайней мере в 10 раз.

Пусть последняя цифра числа отлична от 0 и 4. В таблице показано, как меняется последняя цифра при применении В′ (операция В′, т. е. увеличение числа в 2 раза, обозначена чёрной стрелкой, возможность применения А′ или Б′ — красной стрелкой): $$ \def\rto{\textcolor{red}\to} \begin{array}{l} 0\rto\\ 1\to2\to4\rto\\ 2\to4\rto\\ 3\to6\to2\to4\rto\\ 4\rto\\ 5\to0\rto\\ 6\to2\to4\rto\\ 7\to4\rto\\ 8\to6\to2\to4\rto\\ \hline \mathllap{|\enspace}9\to8\to6\to2\to4\rto\mathrel{\mathrlap{\enspace|}}\\ \hline \end{array} $$

Из этой таблицы видно, что если число $N$‍‍ оканчивается на любую цифру, кроме 9, то после не более чем трёхкратного применения В′, т. е. после увеличения не более, чем в 8 раз, к нему можно применить А′ или Б′, т. е. уменьшить его по крайней мере в 10 раз. В итоге из $N$‍‍ получится число, не превосходящее $\dfrac8{10}N\lt N$‍.‍

Осталось рассмотреть лишь числа $N$‍,‍ заканчивающиеся на 9, которые до перехода к А′ увеличиваются в 16 раз. Заметим, что какой бы ни была предыдущая перед 9 цифра числа $N$‍,‍ предпоследняя цифра числа $16N=16(10a+9)=160a+144$‍‍ всегда чётна.

Если эта цифра не 8, то $16N$‍‍ после А′ и не более чем двух операций В′ превратится снова в число с цифрой 0 или 4 на конце, которое мы можем уменьшить по крайней мере в 10 раз. В итоге из $N$‍‍ получится число, не превосходящее $\dfrac{16\cdot4N}{100}\lt N$‍.‍

Остался случай, когда $16N$‍‍ оканчивается на 84. Заметим, что какой бы ни была предыдущая перед 8 цифра этого числа, после операций $$16N=\ldots84\to10b+8\to\to\to80b+64\to8b+6$$ получим число, оканчивающееся на чётную цифру.

Если эта цифра не 8, то не более чем за две операции В мы получаем число с цифрой 0 или 4 на конце, отбрасываем её и в итоге получаем из $N$‍‍ число, не превосходящее $\dfrac{16\cdot8\cdot4}{1000}N\lt N$‍.‍ Если же эта цифра — 8, то за три операции В′ мы получаем число с чётной предпоследней цифрой и из него (после А′, не более чем трёхкратного применения В′ и откидывания последней цифры) — число, не превосходящее $$\dfrac{16\cdot8\cdot8\cdot8}{10\,000}N=\dfrac{8192}{10\,000}N\lt N.$$

Наше утверждение доказано, и задача решена.

Попробуйте, разобравшись в этом решении, перевести с помощью операций A, Б, В число 4 в 1249 (это одно из самых «неприятных» чисел).

Многие читатели, которые решали задачу M140 этим путём, не заметили или не до конца разобрали случай, когда число $N$‍‍ оканчивается на 9.

Значительно более короткое решение придумали А. Асташов (Львов), А. Арсаски (Камо), Г. Высоцкая (Красноярск). Они доказывают, что из любого чётного числа можно с помощью операций A′, Б′, В′ получить меньшее чётное число (ясно, что этого достаточно для решения задачи). Здесь достаточно рассмотреть 5 случаев:

1. $10k\textcolor{red}\to k$‍,‍
2. $10k+2\to20k+4\textcolor{red}\to2k$‍,‍
3. $10k+4\textcolor{red}\to k\to2k$‍,‍
4. $10k+6\to20k+12\to40k+24\textcolor{red}\to4k+2$‍,‍
5. $10k+8\to20k+16\to40k+32\to80k+64\textcolor{red}\to8k+6$‍.‍