0

Пользователь 4chan решил известную математическую проблему при обсуждении аниме

Пользователь 4chan решил известную математическую проблему при обсуждении аниме
В сфере математики есть множество нерешённых проблем, над решением которых учёные бьются десятилетиями. И похоже, что одна из них может получить название "Проблема Харухи", ведь её лучшее решение внезапно появилось на 4chan при обсуждении аниме.

На днях математик и учёный Робин Хьюстон поделился очередным затруднением, с которым столкнулось математическое сообщество: анонимный пользователь форума 4chan опубликовал решение сложной математической проблемы, над которой учёные бьются уже 25 лет, и теперь учёные не знают, как правильно цитировать эту "публикацию".


Интересно, что изначально это обсуждение касалось аниме - пользователи 4chan сумели сформулировать математическую задачу в терминах просмотра эпизодов популярного аниме-сериала “Меланхолия Харухи Судзумии”, который отличается нелинейным повествованием, а потому серии можно смотреть в любом порядке.

В итоге, проблему представили следующим образом:
  • У вас есть n эпизодов сериала. Вы хотите посмотреть эпизоды во всех возможных порядках. Каково минимальное число эпизодов, которое вам придется посмотреть?
  • Повторения допустимы. К примеру, если n = 2, то просмотр 1, 2 и снова 1 эпизодов соответствует критерию.
  • Порядки должны быть продолжающимися. К примеру (1,2,1,3) не включает последовательность (1,2,3).

В таком виде на 4chan эта проблема получила название “Проблемы Харухи” и недавно она была элегантно разрешена анонимным пользователем - с решением можно ознакомиться здесь.

В более формальном (но всё ещё упрощённом) виде проблема звучит несколько иначе, но суть не меняется: какова кратчайшая строка, содержащая все перестановки множества из n элементов. И до недавнего времени у математиков не было элегантного решения этой проблемы. Теперь, благодаря анониму с 4chan, есть.

Также по теме