Гипотеза Коллатца: детская задачка, которую никто не может решить

Правила этой задачи поймёт второклассник, а её решение не далось ни одному математику планеты.

«Опасная задача» — так о ней отзывался Пол Эрдёш, добавляя: математика пока не готова к таким вопросам. И предлагал за решение денежный приз.

Правила игры

Загадайте любое натуральное число. Дальше применяйте всего два правила:

• если число чётное — разделите его пополам;
• если число нечётное — умножьте на 3 и прибавьте 1.

Получившееся число снова прогоните через эти правила. И снова. Гипотеза Коллатца, сформулированная немецким математиком Лотаром Коллатцем в 1937 году, утверждает: с какого бы числа вы ни начали, рано или поздно вы придёте к единице.

Попробуем на числе 6

Возьмём 6 и проследим путь:

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

За восемь шагов добрались до единицы. (Дальше пошёл бы цикл 1 → 4 → 2 → 1, поэтому на единице принято останавливаться.) Возьмём число побольше, 27, — и оно ведёт себя коварно: последовательность взлетает аж до 9232, петляет 111 шагов, но в конце концов всё равно падает к единице.

В чём же сложность

Вот что сводит математиков с ума. Правила тривиальны, но поведение последовательности — настоящие американские горки. Деление на 2 тянет числа вниз, а действие $3n+1$ подбрасывает их вверх. Идёт постоянная борьба двух сил, и заранее не угадать, кто победит на конкретном числе и не унесёт ли его «вверх» навсегда.

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

Никто не нашёл ни такого числа, ни такого цикла. Но «не нашли» — это не доказательство, что их нет.

Компьютеры против гипотезы

А может, просто проверить все числа? Проверили — и не одно. С помощью компьютеров гипотезу подтвердили для всех чисел примерно до $2^{68}$ — это около трёхсот квинтиллионов. Каждое из них честно сходится к единице.

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

def kollatz(n):
    shagi = 0
    pik = n
    while n != 1:
        if n % 2 == 0:
            n //= 2
        else:
            n = 3 * n + 1
        pik = max(pik, n)
        shagi += 1
    return shagi, pik

for start in [6, 7, 27, 97]:
    shagi, pik = kollatz(start)
    print(f"Старт {start:3d}: дошли до 1 за {shagi:3d} шагов, взлетали до {pik}")

Почему её называют опасной

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

Парадокс гипотезы Коллатца в том, что она ломает наше представление о трудности. Мы привыкли: чем сложнее формулировка, тем труднее решение. А тут условие умещается в две строчки для младшеклассника, но за ним — пропасть, дна которой не видно. Это напоминание, что в математике простота вопроса ничего не говорит о простоте ответа.

Что дальше

В 2019 году знаменитый математик Теренс Тао добился крупного частичного результата: он доказал, что «почти все» числа Коллатца опускаются очень близко к единице. Это самый серьёзный прогресс за десятилетия — но всё же не полное доказательство. Гипотеза по-прежнему открыта.

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