Аноним 4chan решил 25-летнюю математическую задачу. Теперь ученые не знают, на кого ссылаться
В сообществе ученых-математиков сейчас обсуждают довольно курьезную ситуацию. На нее в твите указал американский математик Робин Хьюстон. По его словам, лучшее решение известной математической проблемы из области комбинаторики было опубликовано анонимом на популярной имиджборде 4chan. И теперь неясно, как на это решение ссылаться в официальных работах.
A curious situation. The best known lower bound for the minimal length of superpermutations was proved by an anonymous user of a wiki mainly devoted to anime. https://t.co/z3wVAcUJl1
— Robin Houston (@robinhouston) 23 октября 2018 г.
Как Хьюстон позднее сообщил в комментарии The Verge, минуты спустя публикации твита его телефон уже разрывался от сообщений. Это понятно, ведь сама задача — о кратчайших суперперестановках — известна уже 25 лет, она описана, к примеру, в этой работе о построении суперпермутаций и минимальных инъективных суперструн. Суперперестановка — это ряд из всех возможных перестановок, каждая из которых встречается один раз. Кратчайшая суперперестановка — максимально короткий ряд из таких перестановок. Для определения кратчайших суперперестановок есть формула, но она не работает для рядов, где больше пяти цифр.
История с решением задачи началась с обсуждения на 4chan 17 сентября 2011 года, когда один из пользователей задал вопрос: если кто-то захочет посмотреть 14 серий аниме «Меланхолия Харухи Судзумии» в каждом возможном порядке, каким будет минимальное количество серий, которые нужно посмотреть? Дело в том, что у этого аниме — нелинейный сюжет, построенный на путешествиях во времени, и серии можно смотреть в разном порядке. Задача была озаглавлена «Задача Харухи» в честь главной героини аниме.
Описание изначальной задачи и решения до сих пор доступны в сети. Решение уже проверили другие ученые, а Джей Пэнтон из Университета Маркетта даже опубликовал более формальную выкладку, более понятную ученым-математикам вроде него. Обращаясь к изначальной теме на 4chan — любителю аниме придется пересмотреть как минимум 93 884 313 611 серий.
Напомним, ранее мы сообщали, кому дали премии в области медицины, химии, физики. Литературную премию в 2018 отменили из-за скандала с обвинениями в домогательствах.
Комментарии | 2
Ольга, Вы некорректно описали задачу. Если просто найти длину списка всех возможных перестановок из 14 серий, то это будет четырнадцать умножить на факториал от четырнадцати. Однако в таком решении будут возможны ситуации, когда одна серия упоминается в списке два раза подряд, Самый простой пример.
Вариант 1: 1 2 3 4 5 6 7 8 9 10 11 12 13 14
Вариант 2: 14 13 12 11 10 9 8 7 6 5 4 3 2 1
Список из Варианта 1 и Варианта 2: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 14 13 12 11 10 9 8 7 6 5 4 3 2 1.
Так как человек по условиям задачи не обязан смотреть серию 14 два раза подряд, то одно число из общего списка можно исключить.
Но получаются и более сложные ситуации «экономии» списка.
Вот простой пример: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1 .
В этом списке всего 15 серий, но он включает сразу два варианта просмотра сезона по 14 серий (первый вариант: посмотреть серии 1-14, второй вариант: посмотреть серии 2-14, а потом серию номер 1).
В итоге всех «экономий» длину списка с тринадцатизначного числа (14*14!) удается сократить до одинадцатизначного числа (поверим Вам на слово, что это число приведено в конце статьи без ошибок), то есть более, чем в 10 раз. Но математически найти решение оказывается непросто.
Спасибо за замечание, исправим