Мем, который парализовал университеты: почему простая задача «3x+1» уже век крадет время у лучших умов планеты

Математика полна сложных формул и теорем, для понимания которых требуются годы специального обучения. Однако существуют задачи, правила которых можно объяснить за минуту, но на их решение уходят десятилетия. Самым известным примером такой задачи является гипотеза Коллатца. Эта задача, также известная как проблема «3x+1», остается нерешенной с первой половины двадцатого века, несмотря на усилия тысяч ученых по всему миру.

Суть задачи заключается в простом арифметическом алгоритме. Вы выбираете любое целое положительное число и последовательно выполняете два действия:

1. Если число четное, разделите его на 2.
2. Если число нечетное, умножьте его на 3 и прибавьте 1.

Полученное число становится началом для следующего шага. Гипотеза утверждает, что какое бы число вы ни выбрали изначально, в конечном итоге последовательность действий всегда придет к числу 1.

Как только вы достигнете единицы, алгоритм замкнется в бесконечный цикл: 1 переходит в 4 (поскольку 1 нечетное: 1 * 3 + 1 = 4), 4 делится на 2 и становится 2, а 2 снова делится на 2 и превращается в 1.

Как ведут себя числа: примеры вычислений

Чтобы понять сложность этой задачи, достаточно проследить за поведением разных чисел при прохождении алгоритма.

Если начать с четного числа 12, путь к единице будет быстрым:

12 → 6 → 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1

Всего потребовалось 9 шагов.

Если начать с нечетного числа 7, путь окажется длиннее, а значения будут колебаться:

7 → 22 → 11 → 34 → 17 → 52 → 26 → 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

Здесь потребовалось 16 шагов, а максимальное значение в процессе вычислений достигло 52.

Однако настоящее усложнение начинается на некоторых других небольших числах. Например, если взять число 27, траектория его изменений станет крайне запутанной. Прежде чем опуститься до 1, это число пройдет через 111 шагов вычислений. В процессе оно поднимется до значения 9232, совершит десятки колебаний вверх и вниз, и только после этого придет к единице. Тот факт, что число 27 требует столь длинного пути, показывает, насколько непредсказуем этот простой алгоритм.

История возникновения загадки

История этой задачи началась в 1930-х годах. Немецкий математик Лотар Коллатц во время работы над проблемами теории чисел заинтересовался поведением простых арифметических последовательностей. Он сформулировал гипотезу в 1937 году, но долгое время не публиковал ее официально. Коллатц делился задачей с коллегами устно, записывая ее в блокнотах.

В 1950 году Коллатц представил эту задачу на Международном конгрессе математиков в Кембридже. Это событие послужило началом ее активного распространения в научной среде. Задача быстро стала популярной в ведущих университетах мира. Из-за устного характера передачи в разных странах она получала новые названия. В Гамбургском университете ее называли задачей Коллатца, в Сиракузском университете США — Сиракузской проблемой, а некоторые исследователи называли ее алгоритмом Хассе или проблемой Какутани.

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

Официальное признание среди широкой публики задача получила в 1972 году, когда американский популяризатор науки Мартин Гарднер описал ее в своей регулярной колонке в журнале Scientific American. С этого момента гипотезу начали пытаться решить не только профессиональные математики, но и любители по всему миру.

Почему стандартные методы доказательства не работают

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

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

Существует два теоретических сценария, при которых гипотеза Коллатца окажется неверной:

1. Альтернативный цикл. Возможно, существует такое начальное число, последовательность для которого никогда не приведет к единице, а замкнется в другой повторяющийся круг между какими-то крупными числами.
2. Бесконечный рост. Возможно, существует число, последовательность для которого будет расти до бесконечности, никогда не уменьшаясь до единицы и не замыкаясь в цикл.

Чтобы доказать гипотезу, нужно математически обосновать, что ни один из этих двух сценариев невозможен для абсолютно любого целого положительного числа.

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

Ключевые научные достижения на пути к решению

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

Первый серьезный успех был достигнут в 1976 году американским математиком Рихо Террасом. Он применил методы теории вероятностей к анализу последовательности. Террас доказал, что для почти всех начальных чисел их траектория в какой-то момент гарантированно опустится ниже стартового значения.

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

В 2002 году математики Илья Красиков и Джеффри Лагариас опубликовали работу, в которой уточнили количественные показатели задачи. Они доказали, что среди всех чисел, не превышающих заданное значение x, количество тех чисел, которые гарантированно достигают единицы, растет с увеличением самого x. Их расчеты показали, что доля доказанных чисел составляет не менее x в степени 0,84. Хотя это все еще не охватывало все числа, работа установила строгие рамки для нерешенной части задачи.

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

Например, если вы выберете любое очень крупное число, его последовательность почти наверняка опустится ниже тысячи, ниже миллиона или ниже любого другого выбранного вами фиксированного значения. Это означает, что бесконечный рост чисел практически полностью исключен для подавляющего большинства числового ряда.

Однако даже работа Тао не является полным доказательством гипотезы. В математике утверждение «верно для почти всех чисел» все еще оставляет теоретическую возможность существования исключений на бесконечности.

Компьютерные вычисления и роль искусственного интеллекта

Поскольку человеческий мозг пока не может создать универсальное аналитическое доказательство, ученые надеются на помощь компьютерных алгоритмов и современных технологий.

Существует два направления работы компьютеров над этой задачей:

• Поиск контрпримера. Мощные вычислительные системы и распределенные сети постоянно увеличивают границу проверенных чисел. Если компьютеру удастся найти хотя бы одно число, которое уходит в бесконечность или замкнется в альтернативный цикл, гипотеза Коллатца будет мгновенно опровергнута.
• Автоматический поиск доказательств. Современные алгоритмы машинного обучения способны анализировать миллионы шагов различных последовательностей и искать в них скрытые закономерности, которые упускают люди. Искусственный интеллект может помочь ученым найти новые математические правила взаимодействия сложения и умножения, что позволит построить строгое доказательство.

Примером такого потенциала стала недавняя работа нейросетей компании OpenAI, которые смогли обнаружить контрпример для сложной математической задачи, остававшейся нерешенной более 80 лет. Этот случай показал, что искусственный интеллект способен находить решения в теоретических областях, которые долгое время казались людям непреодолимыми.

Значение гипотезы для современной науки

Гипотеза Коллатца часто воспринимается как простая арифметическая игра. Однако ее решение имеет глубокое значение для всей математической науки. Эта задача указывает на фундаментальные пробелы в нашем понимании самых основ арифметики — взаимодействия процессов сложения и умножения.

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

До тех пор, пока решение не найдено, задача «3x+1» остается главным напоминанием о том, что даже самые простые правила могут скрывать в себе неисчерпаемую сложность.