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
8355
Цюрих
(правила перехода внимательно не смотрел)
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
8355
Цюрих
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
8355
Цюрих
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
8355
Цюрих
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
8355
Цюрих
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  След.

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



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

Сейчас этот форум просматривают: Bing [bot]


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

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