Доказательство гипотезы Коллатца при помощи теории игр

Гипо́теза Ко́ллатца (3n+1 диле́мма, сираку́зская пробле́ма) — одна из нерешённых проблем математики. Получила широкую известность благодаря простоте формулировки. Названа по имени немецкого математика Лотара Коллатца, сформулировавшего похожую задачу 1 июля 1932 года[1].

https://ru.wikipedia.org/wiki/%D0%93%D0%B8%D0%BF%D0%BE%D1%82%D0%B5%D0%B7%D0%B0_%D0%9A%D0%BE%D0%BB%D0%BB%D0%B0%D1%82%D1%86%D0%B0

Берём любое натуральное число n. Если оно чётное, то делим его на 2, а если нечётное, то умножаем на 3 и прибавляем 1 (получаем 3n + 1). Над полученным числом выполняем те же самые действия, и так далее.

Гипотеза Коллатца заключается в том, что какое бы начальное число n мы ни взяли, рано или поздно мы получим единицу

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

1) С точки зрения теории игр рассмотрим две стороны конфликта стартовое число, которое рассматриваем и супер ЭВМ, которое его обрабатывает согласно автомату гипотезы Коллатца (или делим или умножаем). Раундом назовем одну операцию деление или умножение. Если было деление то победа ЭВМ, если умножение, то стартового числа.

С точки зрения числа, которое нельзя свести к 1 за любое число операций, то для него приоритетно побеждать в раундах, или как минимум, выиграть максимальное число раундов, если вероятность победы равна 0. Если определим максимальное число раундов, то с точки зрения теории игр, докажем что победить число не может, и вот лучшая стратегия. То есть интерес для нас имеет не само изначальное число, а сходимость разрядности числа при обработке таким двоичным автоматом Коллатца .

Рассмотрим совершенно любое число вида 1(П)0, в двоичной системе счисления, где 1 старший бит, далее бесконечная последовательность, и последний бит равен 0 /1.

В таком виде, задача принимает немного другой поворот, а именно свести разрядность стартового числа к 1. Деление уменьшает размерность на 1, а умножение увеличивает, но 3N+1 <= 4N , поэтому увеличение идет не больше чем на 2 разряда.

2) Рассмотрим тогда на примере числа 1(0)N, что деление на 2 это сдвиг вправо, после числа шагов N мы получим 1. Это плохая стратегия, она сразу ведет нас к поражению.

1(10)N, сводится к 1(01)N, что за один шаг умножение сводим к 1(0)2N, тогда после числа шагов N мы получим 1. Это плохая стратегия, она сразу ведет нас к поражению.

3) Стартовое число бинарное и содержат только 1 и 0. Рассмотрим совершенно любое число, представим его в двоичном виде, разбив на 4 разрядные слова, аналогично 16-ричной системе счисления, для удобства обозначения.

Представим цифровой автомат, состоящий из 16 графов позиций, которые представляют последние 4 разряда числа. И посмотрим переходы между позициями графов в рамках наших преобразования в автомате.

На первом шаге рассмотрения произвольного числа нас интересует последний разряд.

Если он равен 0. То сдвигаем его. Разрядность уменьшается на 1. Тогда преобразование происходит к следующим в скобках значениям в зависимости от старшего разряда

0 (0 8)

2 (1 9)

4 (2 A)

6 (3 B)

8 (4 C)

A (5 D)

C (6 E)

E (7 F)

Выбор этих позиций проигрышная стратегия для стартового числа.

Таким образом, 16 стартовых позиций сходится к 8, тем что заканчиваются на 1.

Если он равен 1. То производим у(х) = 3N+1 над оставшимися 8 позициями. Рассмотрим каждую отдельно.

Рассмотрение каждой из 8 позиций автомата, которые преобразуются через у(х).

Позиция графа (0001)

0001

*

0011

_

0001

0010

_

0011

+

0001

_

0100

Уменьшает разрядность, Разрядность +1, затем - 2.

....

Позиция графа (0011)

0011

*

0011

_

0011

0110

_

1001

+

0001

_

1010

Уменьшает разрядность, Разрядность +1, затем - 1.

Переход либо

0101

1101

....

Позиция графа (0101)

0101

*

0011

_

00101

01010

_

01111

+

00001

_

10000

Уменьшает разрядность, Разрядность +1, затем - 4.

....

Позиция графа (0111)

0111

*

0011

_

00111

01110

_

10001

+

00001

_

10010

Уменьшает разрядность, Разрядность +1, затем - 1.

....

Переход

1001

0001

И так далее.

4) Кратко итог

Стартовое число (Первая итерация y(x) разрядность+2) (разрядность -1) (разрядность -1)

1 (4) (2 A) (1 9 5 D)

3 (A) (5 D) (0 8)

5 (0) (0 8) (0 4 C)

7 (6) (3)

9 (C) (6 E) (3 B 7 F)

B (2) (1 9) (4 C)

D (8) (4 C) (4 2 A)

F (E) (7 F) (0 7 F)

Таким образом, из 8 позиций 7 на каждом шаге не побеждают, и в некоторых случаях проигрывают. Единственная стратегия увеличивающая стабильно разрядность сводится к максимуму 1 в числе.

Тогда только одна позиция 1111 не сводится однозначно к предыдущим автоматам, а имеет зависимость от старших бит числа.

Это граф может быть само зацикленным, если старший разряд 1, или сводится к позиции (0111), если старший разряд 0.

Таким образом, делаем вывод что любой конец числа после преобразования исходного автомата уменьшает или не увеличивает разрядность исходного, числа кроме F(1111) только если старший бит при этом 1, и следующий за ним тоже 1.

Таким образом, только число формата 1(1)N. Где разрядность стремится к бесконечности не уменьшает разрядность, а увеличивает каждый шаг разряд. Это единственная выигрышная стратегия, остальные будут ей проигрывать.

5) Тогда подробно рассмотрим этот случай. Может ли число 1(1)N - выиграть автомат Коллатца и зациклиться?

После первого преобразования

1(1)1 через у(х)и один сдвиг.

10(1)1. = 1 (0)1 (1)N , разрядность N +1 .

1 (0)3 (1)N-2. , разрядность N +2.

1(10)2 (1)N-2 , разрядность N +3.

1 01 (0)4 (1)N-3 , разрядность N +3.

1(10)4 (1)N-4 , разрядность N +4.

1 01 (0)6 (1)N-4 , разрядность N +4

Закономерность уже видна, на N шаге получим разрядность N + N = 2N

1(10)N (1)0 = 1(10)N

1(10)N, сводится к 1(01)N, что за один шаг умножение сводим к 1(0)2N, тогда после числа шагов 2N мы получим 1. Это лучшая стратегия,но и она ведет нас к поражению.

Тогда любое число сведено к 1(0).

Что и требовалось доказать.

Разрядность числа будет уменьшаться при любом случае. Любое число после преобразования этим автоматом сводится к 1 или тождественному случаю 1(0)N.

Гипотеза доказана. Любое число будет сведено к виду 1(0)N, что после деления тождественно 1.