Сиракузская проблема, идея для решения (часть 1)

Сиракузская проблема — одна из странных проблем, нерешенных до сих пор. Вроде бы простая задача сформулированная так:

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

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

Иное название — гипотеза Коллатца.

В вопросах решения — эта одна из тех задач, которые с кажущейся простотой решения получаются совсем не простыми. А учитывая, что используют вероятностные подходы, то и в некоторых ситуациях избыточно сложные, хотя формулировка такая, что каждый школьник поймет. Схожая ситуация была с Великой Теоремой Ферма, которая, несмотря на то, что имело простую формулировку, потребовала больше 300 лет, не 120 страниц работ Уайлса и математику алгебраической теории групп в теории чисел, которая явно была не доступна в 17-м веке. В итоге решение породило ферматистов, или тех самых людей, которые пытаются найти простое решение для простой задачи. Ну а репутация о них…

С гипотезой Коллатца скорее всего судьба будет схожая, учитывая какие методы используют передовые математики мира для доказательства. Поэтому интересно взглянуть на задачу с другой стороны. В этой части мы посмотрим несколько идей-подзадач, которые может облегчат воприятие задачи и дадут возможность решить задачу как можно проще. Эти идеи — одни из элемнтов именно в конструктивном, а не аналитическом подходе к решению задачи.

Идея №1 . Двоичное представление

Если внимательно рассмотреть условие и его математическое представление, то можем заметить:

1. Разделение чисел на четные и нечетные числа

2. В одном из преобразований мы делим число на 2

3. 1,2 и 4 — это степени двойки.

Эти замечания подсказывают нам — представь все числа в двоичной системе. И вправду, тогда первое преобразование — это просто забор последнего нуля из числа, а 1, 2 и 4 — это 1,10 и 100 в двоичном представлении, которые схожи количеством единиц в числе.

Тут стоит сказать, что на самом деле задача для нас заканчивается тогда, когда получаем число вида 2^n (2^n «яма»). Тогда через n шагов получаем первым преобразованием единицу. И тогда для доказательства нам надо убедиться, что количество единиц в числе после преобразований уменьшается и доходит до единицы. И если с первым преобразованием это понятно (количство единиц не изменяется, а количество цифр уменьшается), то со вторым преобразованием явно это мы не можем сказать.

Расмотрим это преобразование повнимательнее. С +1 мы явно можем сказать, что для нечетных чисел, это преобразование если не уменьшают количество единиц (например если заканчивается на блок единиц), то уж точно не увеличивает (заменяя 01 на 10 в конце). Тогда вся магия проблемы заключается в умножении нечетного числа на 3. И это неудивительно — 3 для двоичной системы то же самое, что и 11 для десятеричной. А мы помним, что результат умножения 11 на какое-либо число — это крайние цифры исходного числа и суммы соседних цифр между ними с нюансами перехода через десяток. А в упрощённой двоичной системе наверное всё ещё проще, не так ли?

Ну так давайте рассмотрим умножение на 11 (тройку) любого числа. И если с нулем неинтересно — количество единиц не изменяется, то возьмем блок единиц и умножим на 11:

И видим интересную особенность: вторая с конца единица мигрирует на n+2 позицию. И получается что количество единиц не уменьшается. А если получается набор единиц в конце, то после сложение с единицей, то весь блок единиц заменяется на нули (вспомните преобразование в дереве Фенвика). Вроде по логике получается, что количество единиц уменьшается (особенно если блоки пересекаются). Но как только на практике посмотрим, взяв как пример число 5 (101). Итак, умножим число на 3 и получим 15 (1111). Как видим количество единиц не только не уменьшилось, но и увеличилось в 2 раза. Как так происходит? Вся проблема кроется в маленькой детали: мы умолчали ситуацию, когда n=1. То есть блоки длиной в 1 единицу удваиваются за счет добавления единиц перед каждым блоком. А это говорит о том, что 1 — это именно предел последовательности, а значит и все сопутствующие параметры и теоремы для математического ряда из области математического анализа могут помочь в доказательстве.

Идея №2. Поведение блоков при преобразованиях

Как видим, поведение числа зависит от длины блоков единиц и нулей. И при этом разделить число на двоичные блоки мы можем по поведению этих блоков при 3n преобразовании:

1. Блок нулей, длиной m (a_m)

2. Блок единиц, длиной n (b_n)

3. Блок чередующихся нулей и единиц, длиной k (c_k)

И если с первым и вторым пунктом число в таком виде выглядит более естественно, то вместе с 3-м пунктом требуется понимание того как преобразовывать обычную двоичную запись в наше представление. На самом деле весь секрет представления заключается в переходе от нуля к единице (c-переход). Если после перехода дальше идут единицы, то с этого момента начинается b — блок, а после и a блок, и снова по-новой. Заметим, что переход между b-блоком и a-блоком нам не интересен, поскольку 3n-преобразование влияет на b-блок, а не a-блок. Из этого рассуждения мы можем сказать, что блочное представление будет в нескольких вариантах (для наглядности ограничений запись будет сродни регулярным выраженниям):

1. (с+b*a*)+ (не усложнял ограничение на количство a и b блоков для наглядности. Важно то, что b0a0 блок тут не подходит — хотя бы в одном из них должно быть ненулевое число)

2. (cb*a*)+ (тут ограничений нет, так как один правило составления блока зависит от c-элемента).

   Теперь опишем умножение на 3 в наших терминах:

Как заметим, я немного смухлевал, и добавил в сba -терминалы какую-то единицу, но если посмтреть на длину исходной последовательности, то становится понятно, что это — не единица из b-блока, а единица-инвертор, влияющее на следующие блоки. Это значит, что если в блоке перед ним нету нулей, то b-блок становится a-блоком и 1-инвертор идет дальше. Если в блоке впереди только 1 ноль, то он ставится единицей из b-блока и увеличивает длину b-блока на 1 единицу. А вот если нулей не меньше 2-ух, то инвертор забирает 2 нуля и становится c-блоком.

Теперь видим, что наша задача трансформировалось в доказательство того, что не только количество единиц уменьшается до 1, но и количество блоков умешится в пределе до 1 блока. И если с количеством единиц их количество или уменьшается минимум на 1 единицу, или в 2 раза, то с количеством блоков или уменьшается в несколько раз, или увеличивается максимум в 3 раза. Несмотря на это, интуитивно понятно, что новые c-блоки после последующих преобразований все c-блоки уйдут. И тут требуется аккуратность в доказательстве подобного факта.

Идея № 3. Понятие расстояния между блоками

Последнее, что стоит описать, это как раз понятие расстояния между блоками. Из предыдущего пункта мы поняли то, что 3n-преобразования влияют на b-блоки, при этом не влияя на предыдущие блоки, но при этом забирая нули со следующего блока. При этом когда нули закончатся инвертор начнет менять единицы на нули. А это означает, что после следующего преобразования блок уйдет. То есть по сути нули — это то самое расстояние между блоками, которое изменяется за счет 3n — преобразования. А после достижения этот блок уходит.

Итог

В принципе эти 3 инварианта — уже довольно показательны в поведении чисел при 3n+1 преобразовании в Сиракузской проблеме. Дальнейшее изучение их поведения как минимум усложняет понимание проблемы, а значит следующая часть (которую надеюсь не придется писать) — будет уже связана с прямым доказательством гипотезы.

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