28.10.2018

Задача Харухи Судзумия: анонимус с 4chan дал ответ на важный вопрос из области комбинаторики

Неизвестный автор с аниме-вики решил известную проблему из области комбинаторики, размышляя над последовательностями серий аниме «Меланхолия Харухи Судзумия». Эти серии настолько сюжетно разрозненны, что хронологическая последовательность может быть, теоретически, любой. Чтобы охватить все возможные последовательности наименее затратным путём, пользователь предложил решение, которое, как оказалось, математически верно.

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

Джей Пантон (Jay Panthone), математик и университета Маркетт (Marquette University), перевёл доказательство на 4chan на язык математики и подтвердил, что в нём всё верно. Эту историю обнаружил математик Робин Хьюстон (Robin Houston) и сообщил о ней в своём твиттере 23 октября. «Интересно, – говорит он, – формула наилучшей нижней границы суперперестановок была доказана анонимным пользователем вики, посвящённой аниме. Удастся ли опубликовать статью в научном журнале, где главный автор будет анонимусом с 4chan? Я надеюсь, что да».

Задача: Есть N серий аниме. Вы хотите посмотреть эпизоды во всех возможных последовательностях. Какое будет наименьшее количество просмотренных серий? Повтор последовательностей не допускается. И мы должны посмотреть все такие повторы «за один присест».

Допустим, у нас есть набор, в котором две серии – A и B. Тогда все возможные пермутации (перестановки) – это AB и BA. Для этого ряда суперперестановка – такая строка, в которой будут все возможные перестановки, будет ABA. Если у нас есть серии A, B и C, то всех возможных перестановок будет 6 – ABC, ACB, BAC, BCA, CAB, CBA. И последовательность ABCABACBA – будет самой короткой суперперестановкой с длиной 9. А если у нас есть серии A, B, C и D? Какова будет нижняя граница длины самой короткой суперперестановки?

Ответ: n! + (n−1)! + (n−2)! + n−3 (для n≥2). Аноним приводит алгоритм подсчёта и доказательство правильности формулы. Согласно такой формуле, чтобы посмотреть все возможные хронологические последовательности первого сезона Харухи Судзумия, в котором 14 серий, необходимо посмотреть как минимум 93 924 230 411 серий подряд.

Александра «Renoire» Алексеева

Источники:

1. 22century.ru