Получи число

[Pachemychka Pacman]

Pachemychka Pacman , можно и так.

Значит, я ещё не такой тупой, как хотелось ожидать!
Спасибо за веру! 

[Илья]

Не, я вместо трез раз умножения на 2, умножил два раза, потому и получил сначала, что заканчивается на двойку, а так все верно: 8*2*2*2=64, четверку обрезаем, число уменьшается, что нам и нужно.

[Кадила???]

А то, что до этого умножили разок на 2 для четности числа, уже забыли?

[Илья]

А что делать, если после уменьшения получается нечетное число, которое оканчивается, к примеру, на девятку? Или изначально начинается на девятку, и после тройного удвоения 10n+8 получившееся число больше изначального?

Когда оканчивается на 9-ку нужно четверное удвоение: 9*2*2*2*2=64

[Lkob]

Из числа 10n+8 можно получить 20n+10+6, 40n+30+2, затем 80n+60+4 и 8k + 6.
В данном случае мы еще можем убрать 0.
Думаю, теперь достаточно убедительно. А то, что в начале прийдется умножить на 2, если число нечетное - уже не существенно.

[Кадила???]

Не хочу вас всех расстраивать, но не 64, а 144. Кстате, четверка в десятках - частный случай, при изначальном 29, к примеру, ее не будет.

[Кадила???]

Из числа 10n+8 можно получить 20n+10+6, 40n+30+2, затем 80n+60+4 и 8k + 6.
В данном случае мы еще можем убрать 0.
Думаю, теперь достаточно убедительно. А то, что в начале прийдется умножить на 2, если число нечетное - уже не существенно.

В каком месте 0 появляется? Как может быть несущественным удвоение числа, когда на этом строится доказательство, и число без удвоения уменьшается, а с удвоением увеличивается?

[Lkob]

Как может быть несущественным удвоение числа, когда на этом строится доказательство, и число без удвоения уменьшается, а с удвоением увеличивается?

Если мы умножим на два, но после этого разделим на 10 (уберем 0).
Да, что-то не так. Надо доработать. 

[Илья]

Не хочу вас всех расстраивать, но не 64, а 144. Кстате, четверка в десятках - частный случай, при изначальном 29, к примеру, ее не будет.

29-464-46-52-104-10-1

[Илья]

Предложенное Lkob доказательство абсолютно такое же как в источнике, там еще есть сложное доказательство, но написано, что можно и так.
Кадила?? ? , если считаете по другому, приведите число и я сведу его к единице.

[Lkob]

Предложенное Lkob доказательство абсолютно такое же как в источнике, там еще есть сложное доказательство, но написано, что можно и так.
Кадила?? ? , если считаете по другому, приведите число и я сведу его к единице.

Проблема в том, что доказательство основано на уменьшении числа каждый раз. Но есть один случай, когда оно не уменьшается, а увеличивается. К примеру, число 29:

29-464-46-92-184-18-36-72-144-14-1-2-4.
 

[Илья]

Но в итоге оно же все равно уменьшается, то есть сводится к единице, что нам и нужно.
Или наличие такого "нехорошего" числа, как 29, дает вероятность того, что найдется такое число, которое при выполнении операций по доказателству, каждый раз будет увеличеваться, а не уменьшаться и мы его не сможем свести к единице?

[Lkob]

Но в итоге оно же все равно уменьшается, то есть сводится к единице, что нам и нужно.

Согласен. Если никто не против, можна ли выложить второе доказательство? Интересно посмотреть.

[Илья]

Согласен. Если никто не против, можна ли выложить второе доказательство? Интересно посмотреть.

Сейчас выложу под спойлером.

[Илья]

2. Доказательство:
Показать скрытый текст

Докажем, что если с каждым числом 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


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

P.S.

По-моему, Илья постоянно путает черное и белое, добро и зло, правильное и неправильное.

Забыли добавить про право и лево.