https://meduza.io/feature/2018/10/25/polzovatel-4chan-ob-yasnyal-v-kakom-poryadke-smotret-anime-serial-i-kazhetsya-reshil-zadachu-nad-kotoroy-matematiki-dumali-25-let
Аноним
25/10/18 Чтв 19:36:46
№
1
http://mathsci.wikia.com/wiki/The_Haruhi_Problem
Пользователь 4chan объяснял, в каком порядке смотреть аниме-сериал. И, кажется, решил задачу, над которой математики думали 25 лет
Ученые пытались решить математическую задачу о кратчайших суперперестановках с 1993 года. Чтобы ее понять, не нужно быть математиком. Просто представьте цифры 1, 2, 3. Перестановка — эти три цифры в любом порядке: 123, 213, 321. Всего в этом случае перестановок шесть.
А есть суперперестановка. Это числовой ряд из всех возможных перестановок. Суперперестановку для цифр 1, 2, 3 можно записать в ряд из 18 символов, а можно — из девяти, если наложить перестановки друг на друга. На гифке ниже — кратчайшая суперперестановка для цифр 1, 2, 3. В нее помещаются все комбинации, которые можно составить из этих трех цифр.
Математики вывели формулу для определения кратчайших суперперестановок, но она не работает для рядов, в которых больше пяти цифр. Вывести работающую формулу — это и есть суть задачи о кратчайших суперперестановках.
23 октября математик Робин Хьюстон написал в твиттере, что задача о кратчайших суперперестановках, по всей видимости, давно решена, но математики не используют это решение в своих исследованиях. Все из-за того, что оно опубликовано не в авторитетных научных журналах, а на анонимном форуме 4chan
В сентябре 2011 года на 4chan появился вопрос, касающийся аниме «Меланхолия Харухи Судзумии». Этот сериал посвящен путешествиям во времени и имеет нелинейный сюжет. Его первый сезон вышел в 2006 году, он состоит из 14 эпизодов, которые можно смотреть в произвольном порядке. Фанаты «Меланхолии Харухи Судзумии» пересматривают аниме в разной хронологии. Пользователь 4chan интересовался, какое минимальное количество эпизодов «Меланхолии Харухи Судзумии» нужно посмотреть, чтобы утверждать, что все серии первого сезона были просмотрены в любом возможном порядке.
Анонимный пользователь в комментариях предложил формулу для вычисления. Позже его посты были скопированы на сайт научной онлайн-энциклопедии. Решение пользователя 4chan заметил профессиональный математик Джей Пантон, преподаватель Университета Маркетта в штате Висконсин, — и решил его проверить. Анонимность автора не стала для него проблемой. «Красота математики в том, что ты должен убедить скептически настроенного читателя в своей правоте. Для этого ему необязательно знать твое имя», — заявил Пантон изданию The Verge.
Он пришел к выводу, что решение анонима с 4chan работает. Так как тот предложил только формулу, но не количественный ответ на вопрос про аниме, The Verge попросило Пантона посчитать, сколько же эпизодов «Меланхолии Харухи Судзумии» надо просмотреть, чтобы увидеть все серии первого сезона в любом возможном порядке.
Его ответ — минимум 93884313611 (девяносто три миллиарда восемьсот восемьдесят четыре миллиона триста тринадцать тысяч шестьсот одиннадцать эпизодов).
Нихуя не понял. Давай еще раз.
Где "гифка ниже"?
>Aнонимный пользователь в комментариях предложил формулу для вычисления.
>Решение пользователя 4chan заметил профессиональный математик Джей Пантон
Что он там делал? Вангую, он же сам и решил.
Опять всю новость переврали. Там просто какая-то оценка снизу доказана, точный ответ вроде неизвестен.
Вот другой вопрос, который пришёл мне по прочтении статьи: какую длину имеет минимальная строка, содержащая все перестановки S_n как подпоследовательности (в статье обсуждается вопрос с подстроками). По-моему, n(n-1) + 1: как пример, можно рассмотреть строку из n-1 блока из n подряд идущих элементов 1,2,...,n, а в конце стоит 1.
Так вот. Чому форчанг такой крутой?