Задача М140‍‍‍

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

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

При этом мы будем каждый раз, как только это возможно, применять операцию А′ или Б′, чтобы по возможности на каждом шаге уменьшать наше число. Получим: $$ 1972\rightarrow3944\rightarrow394\rightarrow39\rightarrow 78 \rightarrow 156 \rightarrow 312 \rightarrow 624 \rightarrow 62 \rightarrow 124 \rightarrow 12 \rightarrow 24 \rightarrow 2 \rightarrow 4. $$

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

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

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

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

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

Пусть последняя цифра числа отлична от 0 и 4. В таблице 1 показано, как меняется последняя цифра при применении В′ (операция В′, то есть увеличение числа в 2 раза, обозначена чёрной стрелкой, возможность применения А′ или Б′ — красной стрелкой):

Таблица 1

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

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

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

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

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

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

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

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

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

1. $10k \rightarrow k$‍,‍
2. $10k + 2 \rightarrow 20k + 4 \rightarrow 2k$‍,‍
3. $10k + 4 \rightarrow k \rightarrow 2k$‍,‍
4. $10k + 6 \rightarrow 20k + 12 \rightarrow 40k + 24 \rightarrow 4k + 2$‍,‍
5. $10k + 8 \rightarrow 20k + 16 \rightarrow 40k + 32 \rightarrow 80k + 64 \rightarrow 8k + 6$‍.‍