Суперперестановки и любители аниме

Иногда серьёзная математика возникает совершенно неожиданно. Сегодняшняя история этому пример.

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

Можно сформулировать задачу и по-другому. Если серии пронумеровать буквами (14 разных цифр у нас нет, поэтому берём буквы), то какова минимальная длина огромного слова, в котором присутствует любая из возможных перестановок 14 элементов?

И это вопрос про кратчайшую суперперестановку! Разберёмся, что это такое.

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

Пусть наш алфавит состоит только из двух символов: 1 и 2. Возможны всего две перестановки из этих элементов: 12 и 21. Кратчайшим словом, содержащим обе эти перестановки, будет 121 — в нём встречается и 12, и 21. Слово 212 тоже подходит. Как видно, в суперперестановке разрешён «нахлёст», то есть любой символ может быть частью разных подслов одновременно. Длина кратчайшей суперперестановки двух символов равна 3.

Для алфавита из трёх символов ситуация поинтереснее. Здесь самая короткая суперперестановка имеет длину 9 — например, 123121321.

Составить корректную суперперестановку несложно — можно просто выписать все перестановки одну за другой в виде длинного слова. Но это неспортивно! Математиков, конечно же, интересует кратчайшая из возможных суперперестановок для каждого n.

При n = 4 она имеет длину 33, а при n = 5 — длину 153.

Доказано, что для 1 ⩽ n ⩽ 5 кратчайшая суперперестановка n символов имеет длину 1! + 2! + … + n! (можете убедиться, что будут получаться именно значения 1, 3, 9, 33 и 153).

Для случаев n > 5 данная формула, увы, не работает, и рассчитать точную длину кратчайшей перестановки сложно. Поэтому оценивают её нижнюю и верхнюю границы. Конечно, можно сказать, что нижняя граница равна 1, а верхняя — какому-нибудь большому числу вроде 10^{100}. Но ценности в таком результате мало. Математики хотят получить такие оценки границ, которые максимально близки к точному значению. Другими словами, важно, чтобы нижняя была как можно выше, а верхняя — как можно ниже.

И лучшая из всех доказанных формул для нижней границы родилась именно на имиджборде!

Буквально через час первому фанату ответил другой — он привёл в общем виде формулу для расчёта нижней границы на любое количество эпизодов: n! + (n − 1)! + (n − 2)! + n − 3.

Из его рассуждения следовало, что для первого сезона этого сериала пришлось бы посмотреть не менее 93 884 313 611 серий подряд.

Несколько лет это событие оставалось незамеченным, а потом копию постов увидели математики. Они всё проверили и написали статью с формально оформленным доказательством.

Первым и главным автором они указали Анонимуса с 4chan, ведь имя этого героя до сих пор неизвестно.

Вот такая великолепная история.

Кстати, чтобы посмотреть те 14 эпизодов во всех возможных порядках, потребуется примерно 4 миллиона лет. Запасаемся попкорном!