Формула, рождённая в хаосе: как аниме-фанат опередил профессиональных математиков

Математические решения можно найти в самых неожиданных местах, включая тёмные уголки интернета. В 2011 году анонимный пользователь на ныне печально известном форуме 4chan задал математическую задачу, связанную с культовым аниме-сериалом Меланхолия Харухи Судзумии. Несмотря на репутацию площадки, этот пост привел к открытию нового способа решения сложной математической проблемы.

Первый сезон этого аниме включает 14 эпизодов, которые можно смотреть в любом порядке. (Для тех, кто далёк от мира аниме: восьмисерийный триллер Kaleidoscope на Netflix использует тот же принцип.) В 2011 году в обсуждении на 4chan кто-то задал вопрос: какое минимальное количество эпизодов нужно посмотреть, чтобы охватить все возможные порядки их воспроизведения?

Этот вопрос оказался связан с так называемыми суперпермутациями. Это направление математики до сих пор остаётся загадкой: даже сегодня учёные не могут дать полный ответ на проблему, которую поднял пользователь 4chan.

Однако в том обсуждении один из анонимных пользователей предложил оценку минимального количества просмотренных эпизодов, использовав метод, ранее неизвестный математикам. «Мне потребуется несколько постов, чтобы подробно это объяснить. Посмотрите, не допустил ли я ошибок», — написал пользователь и поэтапно изложил свою идею. Другие участники обсуждения проверили его аргументы и начали их обсуждать, но за пределами 4chan никто не обратил на это внимания.

Экстремальный марафон

В математике два объекта могут менять порядок, переставляясь различными способами. Например, можно поменять местами A и B, получив BA. Если бы аниме состояло всего из двух эпизодов, их можно было бы смотреть в последовательности (1-2) или (2-1).

Если хочется просмотреть сериал во всех возможных порядках, потребуется суперпермутация — последовательность, включающая все возможные перестановки. Представьте себе марафон, где сначала показывают первый эпизод, затем второй, а потом повторяют второй и первый (1-2-2-1). Чтобы избежать повторов подряд, можно использовать более короткую суперпермутацию: 1-2-1. Таким образом, можно обойтись всего тремя эпизодами.

Если сериал состоит из трёх эпизодов, задача усложняется. Всего существует 3! = 6 разных последовательностей: 1-2-3, 1-3-2, 2-3-1, 2-1-3, 3-1-2, 3-2-1. Однако, чтобы охватить их все, не требуется просматривать 3 × 6 = 18 эпизодов — можно найти сокращённый вариант: 1-2-3-1-2-1-3-2-1. В этом порядке содержатся все возможные перестановки чисел 1, 2 и 3, и при этом достаточно всего 9 эпизодов.

Математики уже рассчитали минимальные суперпермутации для сериалов с n = 4 и n = 5 эпизодами (33 и 153 эпизода соответственно). Однако для n > 5 точные решения пока неизвестны.

Эта задача связана с одной из самых сложных проблем алгоритмики — задачей коммивояжёра . В классической формулировке человек хочет посетить несколько городов и вернуться домой, при этом маршрут должен быть минимальной длины. В случае суперпермутаций города представляют собой разные перестановки, а «дистанции» между ними определяются степенью их перекрытия. Например, последовательности 1-2-3 и 2-3-1 имеют значительное пересечение: последние две цифры первой совпадают с первыми двумя цифрами второй, поэтому они объединяются в 1-2-3-1. А вот 1-2-3 и 2-1-3 не имеют такого перекрытия, и их объединение требует всех шести эпизодов.

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

Компьютеры могут вычислять суперпермутации для n = 4 и n = 5, но не для больших значений. Хотя можно найти длинные суперпермутации, отыскать самую короткую чрезвычайно сложно.

Поэтому учёные используют приближённые оценки. Например, один алгоритм предлагает следующую формулу для длины минимальной суперпермутации: 1! + 2! + 3! + ... + n!. Для n = 2 получается 3, для n = 3 — 9, для n = 4 — 33, а для n = 5 — 153. Однако для больших n этот метод переоценивает длину.

Совпадения и переоткрытия

В 2013 году математик Натан Джонстон случайно наткнулся на страницу фанатов Меланхолии Харухи Судзумии. Хотя он сам не был поклонником аниме, его поиск информации о суперпермутациях привёл его к обсуждению, которое было перенесено с 4chan.

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

В 2018 году математик Робин Хьюстон наткнулся на этот пост случайно. Он только что узнал, что австралийский писатель-фантаст Грег Иган вывел новую верхнюю границу для суперпермутаций:

n! + (n – 1)! + (n – 2)! + (n – 3)! + n – 3

Вскоре Хьюстон понял, что нижнюю границу вычислил анонимный пользователь аниме-форума, и поделился этим в Twitter . Он и его коллеги оформили доказательство, опубликовав его в OEIS с авторством «Anonymous 4chan Poster».

Формула анонима дала новый минимум: n! + (n – 1)! + (n – 2)! + n – 3.

Для Меланхолии Харухи Судзумии (14 эпизодов) минимальная суперпермутация составит 93 884 313 611 эпизодов, а максимальная — 93 924 230 411. Полный просмотр занял бы около 4 миллионов лет.