Форум умных людей

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


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


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


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


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


Таблица.1
0-->
1-->2-->4-->
3-->6-->2-->4
4-->
5-->0
6-->2-->4-->
7-->4-->
8-->6-->4-->
9-->8-->6-->2-->4-->4

Из этой таблицы видно, что если число N оканчивается на любую цифру, кроме 9 , то после не более чем трехкратного применения В ' , т.е. после увеличения не более, чем в 8 раз, к нему можно применить А ' или Б ' , т.е. уменьшить его по крайней мере в 10 раз. В итоге из N получится число, не превосходящее        8
                                                                                                                                                              -----N<N .
                                                                                                                                                                10                         
        
Осталось рассмотреть лишь числа N , заканчивающиеся на 9 , которые до перехода к А ' увеличиваются в 16 раз. Заметим, что какой бы ни была предыдущая перед 9 цифра числа N , предпоследняя цифра числа


16N=16 (10a+9)=160a+144

всегда четна.

Если эта цифра не 8 , то 16N после А ' и не более чем двух операций В ' превратится снова в число с цифрой 0 или 4 на конце, которое мы можем уменьшить по крайней мере в 10 раз. В итоге из А ' получится число, не превосходящее
16*4N
------------    <N.
 100


Остался случай, когда 16N оканчивается на 84 . Заметим, что какой бы ни была предыдущая перед 8 цифра этого числа, после операций


16N=... 84 -->  10b+8 -->-->-->    80b+64 -->  8b+6

получим число, оканчивающееся на четную цифру.

Если эта цифра не 8 , то не более чем за две операции В мы получаем число с цифрой 0 или 4 на конце, отбрасываем ее и в итоге получаем из N число, не превосходящее N<N . Если же эта цифра– 8 , то за три операции В ' мы получаем число с четной предпоследней цифрой и из него (после А ' , не более чем трехкратного применения В ' и откидывания последней цифры)– число, не превосходящее

16*8*8*8       8192
-------------N= --------N<N.
10000            10000


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