2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу 1, 2, 3  След.
 
 Доказательство гипотезы 3x+1.
Сообщение29.09.2017, 20:34 


08/12/13
252
Доказательство гипотезы $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$ верна.

 Профиль  
                  
 
 Re: Доказательство гипотезы 3x+1.
Сообщение30.09.2017, 00:45 
Заслуженный участник
Аватара пользователя


16/07/14
8336
Цюрих
(правила перехода внимательно не смотрел)
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$ куда?

 Профиль  
                  
 
 Re: Доказательство гипотезы 3x+1.
Сообщение30.09.2017, 07:46 


08/12/13
252
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).

 Профиль  
                  
 
 Re: Доказательство гипотезы 3x+1.
Сообщение30.09.2017, 10:31 


14/01/11
2916
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)$ единицы.

 Профиль  
                  
 
 Re: Доказательство гипотезы 3x+1.
Сообщение30.09.2017, 15:01 
Заслуженный участник
Аватара пользователя


16/07/14
8336
Цюрих
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}$ таких что число и его образ относительно функции представимы или непредставимы в нужном виде одновременно. И можно из этих функций композицией собрать новый набор такой что для каждого нечетного числа в этом наборе будет определенная на нем функция, образ относительно которой меньше числа.

 Профиль  
                  
 
 Re: Доказательство гипотезы 3x+1.
Сообщение30.09.2017, 16:40 
Заслуженный участник
Аватара пользователя


09/09/14
6328
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 получаются автоматом.

 Профиль  
                  
 
 Re: Доказательство гипотезы 3x+1.
Сообщение30.09.2017, 17:04 
Заслуженный участник
Аватара пользователя


16/07/14
8336
Цюрих
grizzly в сообщении #1252018 писал(а):
Если в числителе какого-нибудь слагаемого поставить двойку раньше нуля, то будет перебор, а если 0 -- то недобор даже при всех остальных двойках.
Мы вроде бы разрешаем произвольные степени двойки в числителе, а не только первую и нулевую?

 Профиль  
                  
 
 Re: Доказательство гипотезы 3x+1.
Сообщение30.09.2017, 17:07 
Заслуженный участник
Аватара пользователя


09/09/14
6328
mihaild в сообщении #1252022 писал(а):
Мы вроде бы разрешаем произвольные степени двойки в числителе, а не только первую и нулевую?
Не обязательно степень двойки -- можно вообще любое число. Просто если числитель больше 2, то мы переходим в старший разряд.

 Профиль  
                  
 
 Re: Доказательство гипотезы 3x+1.
Сообщение30.09.2017, 18:44 


14/01/11
2916
mihaild в сообщении #1251995 писал(а):
У нас есть набор частичных функций на $\mathbb{N}$ таких что число и его образ относительно функции представимы или непредставимы в нужном виде одновременно. И можно из этих функций композицией собрать новый набор такой что для каждого нечетного числа в этом наборе будет определенная на нем функция, образ относительно которой меньше числа.

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

 Профиль  
                  
 
 Re: Доказательство гипотезы 3x+1.
Сообщение30.09.2017, 19:25 
Заслуженный участник
Аватара пользователя


16/07/14
8336
Цюрих
grizzly в сообщении #1252023 писал(а):
Просто если числитель больше 2, то мы переходим в старший разряд
Т.е. по-русски это будет "дробь $\frac{1}{4}$ в троичной системе исчисления бесконечна"? С этим согласен.

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

 Профиль  
                  
 
 Re: Доказательство гипотезы 3x+1.
Сообщение30.09.2017, 20:18 
Заслуженный участник
Аватара пользователя


09/09/14
6328

(Оффтоп)

mihaild в сообщении #1252053 писал(а):
Т.е. по-русски это будет ...
"Семён Семёныч! (с)" :D

 Профиль  
                  
 
 Re: Доказательство гипотезы 3x+1.
Сообщение01.10.2017, 12:38 


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

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

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

 Профиль  
                  
 
 Re: Доказательство гипотезы 3x+1.
Сообщение03.10.2017, 14:36 


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

 Профиль  
                  
 
 Re: Доказательство гипотезы 3x+1.
Сообщение03.10.2017, 15:48 
Заслуженный участник
Аватара пользователя


16/07/14
8336
Цюрих
Volik в сообщении #1252737 писал(а):
$x_{new}=\frac{3x_{old}+1}{2}$, если $x_{old}$ чётно или $x_{new}=\frac{x_{old}}{2}$ в противном случае.
Поясните пожалуйста, зачем начинать с натурального числа $x$, если дальше все $x_{new}$ полуцелые
Потому что наоборот, первое правило применяется к нечетным, второе к четным.

 Профиль  
                  
 
 Re: Доказательство гипотезы 3x+1.
Сообщение03.10.2017, 16:48 


06/08/17
135
mihaild в сообщении #1252753 писал(а):
Потому что наоборот, первое правило применяется к нечетным, второе к четным.

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 34 ]  На страницу 1, 2, 3  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group