С натуральным числом (записываемым в десятичной системе) разрешено проделывать следующие операции:
А) приписать на конце цифру 4;
Б) приписать на конце цифру 0;
В) разделить на 2 (если число чётно).
Например, если с числом 4 проделаем последовательно операции В, В, А и Б, то получим число 140.
а) Из числа 4 получите число 1972.
б) Докажите, что из числа 4 можно получить любое натуральное число.
a) Вместо того чтобы получить с помощью операций А, Б, В из числа 4 число 1972 , мы попробуем получить из числа 1972 число 4 с помощью обратных операций:
А' — вычеркивание цифры 4 в конце;
Б' — вычеркивание цифры 0 в конце;
В' — умножение числа на 2 .
При этом мы будем каждый раз, как только это возможно, применять операцию А' или Б', чтобы по возможности на каждом шаге уменьшать наше число. Получим:
Ясно, что прочитав эту последовательность от конца к началу, мы получим нужный результат. (Операция Б' здесь не используется.)
б) Докажем, что из любого четного числа можно с помощью операций А', Б', В' получить меньшее четное число (ясно, что этого достаточно для решения задачи – рано или поздно мы получим 4). Здесь достаточно рассмотреть 5 случаев:
1) 10k − k,
2) (10k + 2) − (20k + 4) − 2k,
3) (10k + 4) − k − 2k,
4) (10k + 6) − (20k + 10 + 2) − (40k + 20 + 4) − (4k + 2),
5) (10k + 8) − (20k + 10 + 6) − (40k + 30 + 2) − (80k + 60 + 4) − (8k + 6).