Доказательство гипотезы 3x+1.

[Tot]

Доказательство гипотезы $3x+1$.

План.
1] Формулировка гипотезы.
2] Схема доказательства.
3] Правило $\frac{4}{3}y-\frac{1}{3}$
4] Правило $\frac{2}{3}y-1$
5] Правило $\frac{4}{3}y+\frac{1}{3}$
6] Правило $\frac{2}{3}y-\frac{5}{3}$
7] Правило $\frac{2}{3}y-\frac{1}{3}$
8] Существование по правилам.
9] Последовательности гарантированного уменьшения.
10] Вывод.

1] Формулировка гипотезы.
Для натурального числа $x$ задана процедура получения нового значения из старого по схеме:
$x_{new}=\frac{3x_{old}+1}{2}$, если $x_{old}$ чётно или $x_{new}=\frac{x_{old}}{2}$ в противном случае.
Доказать, что для любого $x$ такая процедура после некоторого числа шагов всегда заканчивается $1$.

2] Схема доказательства.
$x$ всегда можно представить в виде $x=2^{\beta}y$, где $y\in\mathbb N, y\mod 2\equiv 1, \beta\in\mathbb Z^+$.
Причём иксы с произвольным $\beta$ эквивалентны в смысле конечного результата процедуры.
Если конечный результат многократного применения процедуры к $y$ равен $1$, то $y$ можно представить в следующем виде.

$$y=\frac{\frac{\frac{\frac{\frac{2^{\alpha_1}-1}{3}2^{\alpha_2}-1}{3}2^{\alpha_3}-1}{3}...}{3}2^{\alpha_n}-1}{3}$$

$n\in\mathbb N; \alpha_1,...,\alpha_n\in\mathbb Z^+$
Приведём к общему знаменателю и разобъём на отдельные степени двойки.

$$y=\frac{2^{\sum_{i=1}^{n}\alpha_i}}{3^{n-1}}-\frac{2^{\sum_{i=2}^{n}\alpha_i}}{3^{n-1}}-\frac{2^{\sum_{i=3}^{n}\alpha_i}}{3^{n-2}}-...-\frac{2^{\alpha_n}}{3}-1 (1)$$

Гипотеза $3x+1$ сводится к гипотезе о том, что в форме $(1)$ представим любой $y$.
Доказательство проведём по схеме:
1) рассмотрим пять правил перехода от одного игрека к другому игреку без потери формы $(1)$ и найдём условия их применения;
2) покажем, что начальное и конечное значения игрека по правилам существуют в форме $(1)$ лишь одновременно;
3) построим последовательности гарантированного уменьшения начального игрека цепочкой правил во всех случаях.
Суть схемы доказательства заключается в следующем. Пусть есть набор правил, при преобразовании игрека по которым сохраняется форма $(1)$. При этом условия существования в этой форме начального и конечного игреков по правилам взаимны. Тогда если для $\forall y\in\mathbb N, y\mod 2\equiv 1$ можно построить цепочку правил, которая гарантированно уменьшает игрек с сохранением формы $(1)$, то в конечном счёте система таких цепочек приводит к единице, то есть из несуществования начального игрека в форме $(1)$ следует несуществование единицы в той же форме, что заведомо даёт противоречие и доказывает утверждение о представимости любого игрека в форме $(1)$.

3] Правило $\frac{4}{3}y-\frac{1}{3} (2.1)$
Пусть дан $y$ в форме $(1)$. При этом $y\mod 3\equiv 1$. Применим $(2.1)$ для получения $y_1$. $\forall y_1\in\mathbb N, y_1\mod 2\equiv 1$.

$$y_1=\frac{2^{2+\sum_{i=1}^{n}\alpha_i}}{3^{n}}-\frac{2^{2+\sum_{i=2}^{n}\alpha_i}}{3^{n}}-\frac{2^{2+\sum_{i=3}^{n}\alpha_i}}{3^{n-1}}-...-\frac{2^{2+\alpha_n}}{9}-\frac{2}{3}-1$$

Получили $y_1$ в форме $(1)$, то есть нет пропусков в степенях тройки знаменателей и в числителях стоят лишь убывающие степени двойки.

4] Правило $\frac{2}{3}y-1 (2.2)$
Пусть дан $y$ в форме $(1)$. При этом $y\mod 3\equiv 0$. Применим $(2.2)$ для получения $y_1$. $\forall y_1\in\mathbb N, y_1\mod 2\equiv 1$.

$$y_1=\frac{2^{1+\sum_{i=1}^{n}\alpha_i}}{3^{n}}-\frac{2^{1+\sum_{i=2}^{n}\alpha_i}}{3^{n}}-\frac{2^{1+\sum_{i=3}^{n}\alpha_i}}{3^{n-1}}-...-\frac{2^{1+\alpha_n}}{9}-\frac{2}{3}-1$$

Получили $y_1$ в форме $(1)$.

5] Правило $\frac{4}{3}y+\frac{1}{3} (2.3)$
Пусть дан $y$ в форме $(1)$. При этом $y\mod 3\equiv 2$. Применим $(2.3)$ для получения $y_1$. $\forall y_1\in\mathbb N, y_1\mod 2\equiv 1$.

$$y_1=\frac{2^{2+\sum_{i=1}^{n}\alpha_i}}{3^{n}}-\frac{2^{2+\sum_{i=2}^{n}\alpha_i}}{3^{n}}-\frac{2^{2+\sum_{i=3}^{n}\alpha_i}}{3^{n-1}}-...-\frac{2^{2+\alpha_n}}{9}-1$$

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

$$y_1=\frac{2^{2+\sum_{i=1}^{n}\alpha_i}}{3^{n}}-\frac{2^{2+\sum_{i=2}^{n}\alpha_i}}{3^{n}}-\frac{2^{2+\sum_{i=3}^{n}\alpha_i}}{3^{n-1}}-...-\frac{2^{2+\alpha_{n-1}+\alpha_n}}{27}-\frac{2^{\alpha_n}}{9}-\frac{2^{\alpha_n}}{3}-1$$

Получили $y_1$ в форме $(1)$.

6] Правило $\frac{2}{3}y-\frac{5}{3} (2.4)$
Пусть дан $y$, подходящий для $(2.1)$ или $(2.2)$. Тогда у $y_1$ будет следующий хвост.

$$-\frac{2^{\{2;1\}+\alpha_n}}{9}-\frac{2}{3}-1$$

$\forall y_1\in\mathbb N, y_1\mod 2\equiv 1$. Применяется один элемент из множества в фигурных скобках. Пусть $y_1\mod 3\equiv 1$.
Применим $(2.4)$ к $y_1$ для получения $y_2$. $\forall y_2\in\mathbb N, y_2\mod 2\equiv 1$. Хвост у $y_2$ будет следующий.

$$-\frac{1+2^{\{2;1\}+\alpha_n}}{27}-\frac{4}{9}-\frac{2}{3}-1$$

Получили $y_2$ в форме $(1)$.

7] Правило $\frac{2}{3}y-\frac{1}{3} (2.5)$
Пусть дан $y$ в форме $(1)$. При этом $y\mod 3\equiv 2$, a $\alpha_n\neq 0$. Применим $(2.5)$ для получения $y_1$. $\forall y_1\in\mathbb N, y_1\mod 2\equiv 1$.

$$y_1=\frac{2^{1+\sum_{i=1}^{n}\alpha_i}}{3^{n}}-\frac{2^{1+\sum_{i=2}^{n}\alpha_i}}{3^{n}}-\frac{2^{1+\sum_{i=3}^{n}\alpha_i}}{3^{n-1}}-...-\frac{2^{1+\alpha_n}}{9}-1$$

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

$$y_1=\frac{2^{1+\sum_{i=1}^{n}\alpha_i}}{3^{n}}-\frac{2^{1+\sum_{i=2}^{n}\alpha_i}}{3^{n}}-\frac{2^{1+\sum_{i=3}^{n}\alpha_i}}{3^{n-1}}-...-\frac{2^{1+\alpha_{n-1}+\alpha_n}}{27}-\frac{2^{\alpha_n-1}}{9}-\frac{2^{\alpha_n-1}}{3}-1$$

Получили $y_1$ в форме $(1)$.

8] Существование по правилам.
При применении правил из существования начального значения в форме $(1)$ следует существование конечного значения в той же форме. Покажем, что из несуществования начального значения в форме $(1)$ следует несуществование конечного значения в той же форме. Предположим, что это не так, то есть из несуществования начального значения в форме $(1)$ следует существование конечного значения в той же форме. К конечному значению применим обратную операцию с свободным членом правила. Если полученное число делится нацело на $2$, если в правиле коэффициент $\frac{2}{3}$, или на $4$, то исходное предположение ложно, а если нет, то начальное значение не является целым. Следовательно, из несуществования начального значения в форме $(1)$ следует несуществование конечного значения в той же форме.

9] Последовательности гарантированного уменьшения.
Пусть дан $\forall y\in\mathbb N, y\mod 2\equiv 1$. Покажем, что если $y>1$, то всегда можно построить цепочку правил, которая уменьшает $y$. При этом из существования $y$ в форме $(1)$
следует существование конечного значения цепочки в той же форме. При этом последовательность уменьшения не обязательно начинать с $y$, так как вопрос существования $y$ и конечного значения решается так же и при нахождении $y$ внутри цепочки.
Имеем $7$ последовательностей уменьшения, которые исчерпывают все случаи ($k\in\mathbb Z^+$, все элементы цепочек натуральны и нечётны).
1)

$$6k+3\stackrel{\frac{2}{3}y-1}{\longrightarrow}4k+1$$

2)

$$18k+1\stackrel{\frac{4}{3}y-\frac{1}{3}}{\longrightarrow}24k+1\stackrel{\frac{2}{3}y-\frac{5}{3}}{\longrightarrow}16k-1$$

3)

$$18k+7\stackrel{\frac{4}{3}y-\frac{1}{3}}{\longrightarrow}24k+9\stackrel{\frac{2}{3}y-1}{\longrightarrow}16k+5$$

4)

$$18k+13\stackrel{\frac{4}{3}y-\frac{1}{3}}{\longrightarrow}24k+17\stackrel{\frac{2}{3}y-\frac{1}{3}}{\longrightarrow}16k+11$$

5)

$$27k+9\stackrel{\frac{2}{3}y-1}{\longrightarrow}18k+5\stackrel{\frac{2}{3}y-\frac{1}{3}}{\longrightarrow}12k+3$$

6)

$$18k+11\stackrel{\frac{4}{3}y+\frac{1}{3}}{\longrightarrow}24k+15\stackrel{\frac{2}{3}y-1}{\longrightarrow}16k+9$$

7)

$$27k+27\stackrel{\frac{2}{3}y-1}{\longrightarrow}18k+17\stackrel{\frac{2}{3}y-\frac{1}{3}}{\longrightarrow}12k+11$$

10] Вывод.
Для $\forall y\in\mathbb N, y\mod 2\equiv 1$ существует цепочка преобразований, которая приводит к единице и каждый элемент которой представим в форме $(1)$ при условии существования представления в форме $(1)$ единицы. Но ведь единица в этой форме представима. Поэтому $\forall y\in\mathbb N, y\mod 2\equiv 1$ представим в форме $(1)$. А это значит, что гипотеза $3x+1$ верна.

[mihaild]

(правила перехода внимательно не смотрел)

Tot в сообщении #1251847 писал(а):

Предположим, что это не так, то есть из несуществования начального значения в форме $(1)$ следует существование конечного значения в той же форме. К конечному значению применим обратную операцию с свободным членом правила. Если полученное число делится нацело на $2$, если в правиле коэффициент $\frac{2}{3}$, или на $4$, то исходное предположение ложно, а если нет, то начальное значение не является целым.

Вот это непонятно.
Правда ли, что тут говорится, что если $y$ - нечетное целое, $y_1$ получается из $y$ по одному из правил и $y_1$ представимо в нужном виде, то и $y$ представимо в нужном виде?
Скажем, для правила $2.1$: $y = \frac{1}{4}\left(3y_1 + 1\right)$. Почему оно представляется в нужном виде?

Tot в сообщении #1251847 писал(а):

Имеем $7$ последовательностей уменьшения, которые исчерпывают все случаи ($k\in\mathbb Z^+$, все элементы цепочек натуральны и нечётны).

А скажем $23 = 18\cdot 1 + 5$ куда?

[Tot]

mihaild в сообщении #1251891 писал(а):

Правда ли, что тут говорится, что если $y$ - нечетное целое, $y_1$ получается из $y$ по одному из правил и $y_1$ представимо в нужном виде, то и $y$ представимо в нужном виде?

Да, но ещё говорится о факте, который можно сформулировать в виде леммы.
Лемма.
$\frac{1}{4}, \frac{1}{2}, \frac{3}{4}$ нельзя разложить в конечный ряд по степеням $\frac{1}{3}$.
Доказывать не будем.

mihaild в сообщении #1251891 писал(а):

Скажем, для правила $2.1$: $y = \frac{1}{4}\left(3y_1 + 1\right)$. Почему оно представляется в нужном виде?

Давайте рассмотрим.

$$y_1=\frac{2^{\sum_{i=1}^{n}\alpha_i}}{3^{n-1}}-\frac{2^{\sum_{i=2}^{n}\alpha_i}}{3^{n-1}}-\frac{2^{\sum_{i=3}^{n}\alpha_i}}{3^{n-2}}-...-\frac{2^{\alpha_n}}{3}-1$$

$$y=\frac{1}{4}(\frac{2^{\sum_{i=1}^{n}\alpha_i}}{3^{n-2}}-\frac{2^{\sum_{i=2}^{n}\alpha_i}}{3^{n-2}}-\frac{2^{\sum_{i=3}^{n}\alpha_i}}{3^{n-3}}-...-\frac{2^{\alpha_{n-1}+\alpha_n}}{3}-2^{\alpha_n}-2)$$

При $\alpha_n=1$ $y$ в нужной форме существует, в противном случае $y$ не является целым, как и сказано в стартовом сообщении.

mihaild в сообщении #1251891 писал(а):

А скажем $23 = 18\cdot 1 + 5$ куда?

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

[Sender]

Tot в сообщении #1251847 писал(а):

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

$$y=\frac{2^{\sum_{i=1}^{n}\alpha_i}}{3^{n-1}}-\frac{2^{\sum_{i=2}^{n}\alpha_i}}{3^{n-1}}-\frac{2^{\sum_{i=3}^{n}\alpha_i}}{3^{n-2}}-...-\frac{2^{\alpha_n}}{3}-1 (1)$$

Хм, почему это последний член здесь равен $-1$, а не $-\frac{1}{3}$?

-- Сб сен 30, 2017 11:04:57 --

Tot в сообщении #1251847 писал(а):

Тогда если для $\forall y\in\mathbb N, y\mod 2\equiv 1$ можно построить цепочку правил, которая гарантированно уменьшает игрек с сохранением формы $(1)$, то в конечном счёте система таких цепочек приводит к единице

Но ведь для этого $y$ изначально должен быть представим в форме $(1)$.
Если он представим, то он, очевидно, в конечном счёте придёт к единице.

Tot в сообщении #1251847 писал(а):

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

Верно. Однако отсюда никак не следует

Tot в сообщении #1251847 писал(а):

10] Вывод.
Для $\forall y\in\mathbb N, y\mod 2\equiv 1$ существует цепочка преобразований, которая приводит к единице и каждый элемент которой представим в форме $(1)$ при условии существования представления в форме $(1)$ единицы.

[mihaild]

Tot в сообщении #1251912 писал(а):

Доказывать не будем.

Когда я вижу "доказывать не будем" про утверждение, которое я не могу доказать за $10$ секунд в простом решении сложной задачи, у меня тут же возникают подозрения...

Tot в сообщении #1251847 писал(а):

$n\in\mathbb N; \alpha_1,...,\alpha_n\in\mathbb Z^+$

$\mathbb{Z}^+$ - это неотрицательные целые числа? Тогда почему $\alpha_i = 0$ проходит? Если мы делаем преобразование, обратное $\frac{3n + 1}{2}$, то у нас тут же появляется двойка хотя бы в первой степени.

Tot в сообщении #1251912 писал(а):

При $\alpha_n=1$ $y$ в нужной форме существует, в противном случае $y$ не является целым

Тоже как минимум неочевидно.

Sender в сообщении #1251944 писал(а):

Верно. Однако отсюда никак не следует

Тут как раз всё нормально. У нас есть набор частичных функций на $\mathbb{N}$ таких что число и его образ относительно функции представимы или непредставимы в нужном виде одновременно. И можно из этих функций композицией собрать новый набор такой что для каждого нечетного числа в этом наборе будет определенная на нем функция, образ относительно которой меньше числа.

[grizzly]

mihaild в сообщении #1251995 писал(а):

у меня тут же возникают подозрения

upd.
Для $1/2$ очевидно, поскольку $1/2=\sum _1^\infty 1/3^k$. Если в числителе какого-нибудь слагаемого поставить двойку раньше нуля, то будет перебор, а если 0 -- то недобор даже при всех остальных двойках.

-- 30.09.2017, 16:56 --

Для 1/4 тоже не должно быть сложно. 1/4 даёт ряд $2/9^k$ и для этого ряда проходят подобные аргументы; только нужно аккуратно посмотреть почему нельзя нигде поставить больше 2 в числителе (я как-то сразу тоже не соображу, но сомнений у меня нет). 3/4 получаются автоматом.

[mihaild]

grizzly в сообщении #1252018 писал(а):

Если в числителе какого-нибудь слагаемого поставить двойку раньше нуля, то будет перебор, а если 0 -- то недобор даже при всех остальных двойках.

Мы вроде бы разрешаем произвольные степени двойки в числителе, а не только первую и нулевую?

[grizzly]

mihaild в сообщении #1252022 писал(а):

Мы вроде бы разрешаем произвольные степени двойки в числителе, а не только первую и нулевую?

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

[Sender]

mihaild в сообщении #1251995 писал(а):

У нас есть набор частичных функций на $\mathbb{N}$ таких что число и его образ относительно функции представимы или непредставимы в нужном виде одновременно. И можно из этих функций композицией собрать новый набор такой что для каждого нечетного числа в этом наборе будет определенная на нем функция, образ относительно которой меньше числа.

А, теперь понимаю. Более того, могу подтвердить полноту покрытия нечётных чисел рассмотренными случаями 1-7 из пункта 9. Тем не менее, это не снимает моего первого замечания.
И если по поводу правил $\frac{4}{3}y-\frac{1}{3}$ и $\frac{2}{3}y-\frac{1}{3}$ вопросов не возникает, остальные пока что вызывают недоумение.

[mihaild]

grizzly в сообщении #1252023 писал(а):

Просто если числитель больше 2, то мы переходим в старший разряд

Т.е. по-русски это будет "дробь $\frac{1}{4}$ в троичной системе исчисления бесконечна"? С этим согласен.

Итого текущие замечания:
-допустимость $\alpha_i = 0$
-почему последний член в разложении $y$ - $1$, а не $\frac{1}{3}$
-корректность всех правил (надо смотреть внимательно)
-обратимость всех правил (надо смотреть еще внимательнее, но пока что некуда)

[grizzly]

(Оффтоп)

mihaild в сообщении #1252053 писал(а):

Т.е. по-русски это будет ...

"Семён Семёныч! (с)"

[Tot]

mihaild в сообщении #1252053 писал(а):

Итого текущие замечания:
-допустимость $\alpha_i = 0$
-почему последний член в разложении $y$ - $1$, а не $\frac{1}{3}$
-корректность всех правил (надо смотреть внимательно)
-обратимость всех правил (надо смотреть еще внимательнее, но пока что некуда)

1) Фатальная ошибка, нужно подбирать другую систему правил.
2) Устранимая ошибка, перенесём самый нижний знаменатель влево, начальное число в системе цепочек будет всегда кратно трём.
3) Были корректны, попытаюсь построить новую корректную систему под уточнённую нужную форму.
4) Обратимость нужно явно выписывать в описаниях правил. Лемму с доказательством тоже куда-нибудь вставить.

Благодарю всех за внимание. Тайм-аут на несколько дней.

[Volik]

Для натурального числа $x$ задана процедура получения нового значения из старого по схеме:
$x_{new}=\frac{3x_{old}+1}{2}$, если $x_{old}$ чётно или $x_{new}=\frac{x_{old}}{2}$ в противном случае.
Поясните пожалуйста, зачем начинать с натурального числа $x$, если дальше все $x_{new}$ полуцелые?

[mihaild]

Volik в сообщении #1252737 писал(а):

$x_{new}=\frac{3x_{old}+1}{2}$, если $x_{old}$ чётно или $x_{new}=\frac{x_{old}}{2}$ в противном случае.
Поясните пожалуйста, зачем начинать с натурального числа $x$, если дальше все $x_{new}$ полуцелые

Потому что наоборот, первое правило применяется к нечетным, второе к четным.

[Volik]

mihaild в сообщении #1252753 писал(а):

Потому что наоборот, первое правило применяется к нечетным, второе к четным.

И как дальше разбираться, если и дальше будет, пишется одно, а подразумевается наоборот?