Доказательство гипотезы

.
План.
1] Формулировка гипотезы.
2] Схема доказательства.
3] Правило

4] Правило

5] Правило

6] Правило

7] Правило

8] Существование по правилам.
9] Последовательности гарантированного уменьшения.
10] Вывод.
1] Формулировка гипотезы.
Для натурального числа

задана процедура получения нового значения из старого по схеме:

, если

чётно или

в противном случае.
Доказать, что для любого

такая процедура после некоторого числа шагов всегда заканчивается

.
2] Схема доказательства.

всегда можно представить в виде

, где

.
Причём иксы с произвольным

эквивалентны в смысле конечного результата процедуры.
Если конечный результат многократного применения процедуры к

равен

, то

можно представить в следующем виде.


Приведём к общему знаменателю и разобъём на отдельные степени двойки.

Гипотеза

сводится к гипотезе о том, что в форме

представим любой

.
Доказательство проведём по схеме:
1) рассмотрим пять правил перехода от одного игрека к другому игреку без потери формы

и найдём условия их применения;
2) покажем, что начальное и конечное значения игрека по правилам существуют в форме

лишь одновременно;
3) построим последовательности гарантированного уменьшения начального игрека цепочкой правил во всех случаях.
Суть схемы доказательства заключается в следующем. Пусть есть набор правил, при преобразовании игрека по которым сохраняется форма

. При этом условия существования в этой форме начального и конечного игреков по правилам взаимны. Тогда если для

можно построить цепочку правил, которая гарантированно уменьшает игрек с сохранением формы

, то в конечном счёте система таких цепочек приводит к единице, то есть из несуществования начального игрека в форме

следует несуществование единицы в той же форме, что заведомо даёт противоречие и доказывает утверждение о представимости любого игрека в форме

.
3] Правило

Пусть дан

в форме

. При этом

. Применим

для получения

.

.

Получили

в форме

, то есть нет пропусков в степенях тройки знаменателей и в числителях стоят лишь убывающие степени двойки.
4] Правило

Пусть дан

в форме

. При этом

. Применим

для получения

.

.

Получили

в форме

.
5] Правило

Пусть дан

в форме

. При этом

. Применим

для получения

.

.

Преобразуем последнее вычитаемое.

Получили

в форме

.
6] Правило

Пусть дан

, подходящий для

или

. Тогда у

будет следующий хвост.


. Применяется один элемент из множества в фигурных скобках. Пусть

.
Применим

к

для получения

.

. Хвост у

будет следующий.

Получили

в форме

.
7] Правило

Пусть дан

в форме

. При этом

, a

. Применим

для получения

.

.

Преобразуем последнее вычитаемое при

.

Получили

в форме

.
8] Существование по правилам.
При применении правил из существования начального значения в форме

следует существование конечного значения в той же форме. Покажем, что из несуществования начального значения в форме

следует несуществование конечного значения в той же форме. Предположим, что это не так, то есть из несуществования начального значения в форме

следует существование конечного значения в той же форме. К конечному значению применим обратную операцию с свободным членом правила. Если полученное число делится нацело на

, если в правиле коэффициент

, или на

, то исходное предположение ложно, а если нет, то начальное значение не является целым. Следовательно, из несуществования начального значения в форме

следует несуществование конечного значения в той же форме.
9] Последовательности гарантированного уменьшения.
Пусть дан

. Покажем, что если

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

. При этом из существования

в форме

следует существование конечного значения цепочки в той же форме. При этом последовательность уменьшения не обязательно начинать с

, так как вопрос существования

и конечного значения решается так же и при нахождении

внутри цепочки.
Имеем

последовательностей уменьшения, которые исчерпывают все случаи (

, все элементы цепочек натуральны и нечётны).
1)

2)

3)

4)

5)

6)

7)

10] Вывод.
Для

существует цепочка преобразований, которая приводит к единице и каждый элемент которой представим в форме

при условии существования представления в форме

единицы. Но ведь единица в этой форме представима. Поэтому

представим в форме

. А это значит, что гипотеза

верна.