【数学】〈最小超置換問題〉「涼宮ハルヒの憂鬱」のおかげで25年解けなかった数学の難問が解決されるかもしれない

1: 2018/10/25(木) 13:26:58.20 ID:CAP_USER

海外の掲示板「4chan」での議論が、数学者を25年以上悩ませてきた「The Minimal Superpermutation Problem(最小超置換問題)」という難問を解決するかもしれないと、世界中の数学者から大きな関心を集めています。解決の糸口となったのは、テレビアニメ「涼宮ハルヒの憂鬱」のエピソードの視聴順についてでした。
https://i.gzn.jp/img/2018/10/25/suzumiya-haruhi-superpermutation/00.jpg

/sci/ – The Haruhi problem (lower bound) – Science ＆ Math – 4chan
http://boards.4chan.org/sci/thread/10089701/the-haruhi-problem-lower-bound

An anonymous 4chan post could help solve a 25-year-old math mystery – The Verge
https://www.theverge.com/2018/10/24/18019464/4chan-anon-anime-haruhi-math-mystery

2006年に放送されたテレビアニメ「涼宮ハルヒの憂鬱」の第1期は全14話から構成されています。2006年のテレビ放送時では、物語の時系列と異なる順序でエピソードが放映され、話題となりました。

4chanのアニメファンコミュニティの間では「涼宮ハルヒの憂鬱」をどのエピソード順に見るのがよいかという話題がしばしば取り扱われていました。その中で「可能な限りの順序で全てのエピソードを見たい場合、最も少ない組み合わせは何通りになるか」という問題が提起され、このテーマはやがて「Haruhi Problem(ハルヒ問題)」という問題に昇華し、数学コミュニティで議論されるようになりました。このハルヒ問題は、数学の世界では「最小超置換問題」と呼ばれる難問にあたります。

「最小超置換」とは、全ての組み合わせを内包した文字列のこと。例えば、A・Bという2要素の組合せは「AB」と「BA」となりますが、この2文字の最小超置換は「ABA」となります。「ABA」という最小超置換文字列には、「AB」と「BA」という2通りの組み合わせが内包されています。
https://i.gzn.jp/img/2018/10/25/suzumiya-haruhi-superpermutation/aba_m.jpg

また、A・B・Cという3要素の組み合わせは「ABC」「ACB」「BAC」「BCA」「CAB」「CBA」の6通り。そして3文字の最小超置換は「ABCABACBA」という9文字の文字列となります。「ABCABACBA」という文字列には、6通りの組み合わせが全て内包されています。
https://i.gzn.jp/img/2018/10/25/suzumiya-haruhi-superpermutation/abcabacba_m.jpg

続きはソースで

■論文
https://docs.google.com/viewer?a=v&pid=forums&srcid=MTUwMTUxMjExNDk4NTk5NjY5OTkBMDMxNDgwMTA5ODA5OTYyNzcyNDQBdlNFMnM3eTVCUUFKATAuMQEBdjI&authuser=0
http://mathsci.wikia.com/wiki/The_Haruhi_Problem

GIGAZINE
https://gigazine.net/news/20181025-suzumiya-haruhi-superpermutation/