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

この最小超置換の文字列の長さは、要素が増えるごとに爆発的に増えると考えられています。記事作成時点では、最小超置換の文字数は4要素までしか判明していません。最小超置換問題とは、要素の数を「n」と置いたときに最小超置換の文字列の定式化とその証明を求めるというものでした。

この問題が論文で提起されたのは1993年のことでしたが、25年以上かけてこの問題が解決されることはありませんでした。しかし、4chanの数学フォーラムで、nを14とするハルヒ問題の解法をきっかけに証明が投稿され、論文という形式ではないものの、最小超置換問題の解決の糸口となるのではと世界中の数学者から注目を集めました。
https://i.gzn.jp/img/2018/10/25/suzumiya-haruhi-superpermutation/snap0733_m.png

マケット大学の数学者であるジェイ・パントーン氏は、当初この投稿の内容に懐疑的でしたが、この投稿を元にした論文(PDFファイル)を発表しています。パントーン氏によると、「涼宮ハルヒの憂鬱」のエピソードを全組合せで視聴するには少なくとも939億2423万411話のエピソードを見る必要があるとのこと。

また、コンピュータ科学者のロビン・ヒューストン氏は以前から最小超置換問題に取り組んでいた数学者で、ハルヒ問題を皮切りに数学の難問が解き明かされようとしていることについて「興味深い状況だ」と興奮しています。

■論文
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/

引用元: ・http://egg.5ch.net/test/read.cgi/scienceplus/1540441618/

3: ニュースソース検討中@自治議論スレ 2018/10/25(木) 13:32:18.57 ID:SGoLf7Pn
ハルヒが世界を変えた
5: ニュースソース検討中@自治議論スレ 2018/10/25(木) 13:38:52.34 ID:uanqGkYp
バカと天才は紙一重とはホント良く言ったものだなw
6: ニュースソース検討中@自治議論スレ 2018/10/25(木) 13:39:41.26 ID:Kg11SWgE
そもそもどういう構成なのかわからん
7: ニュースソース検討中@自治議論スレ 2018/10/25(木) 13:41:31.00 ID:mAt31iHE
ABOBAかよ
8: ニュースソース検討中@自治議論スレ 2018/10/25(木) 13:41:36.24 ID:H20ia1sP
エンドレスエイトが破壊的すぎて1期の変則放送なんてすっかり忘れていた
9: ニュースソース検討中@自治議論スレ 2018/10/25(木) 13:43:32.66 ID:IwHIlelt
何のこと言っとるか全くわからんがw(^o^)
ず~~~っと考えていたことが「涼宮ハルヒ」を見ていたら
わかったということかwww

よかったねw
10: ニュースソース検討中@自治議論スレ 2018/10/25(木) 13:50:11.57 ID:WyYLDT51
そんな事よりいつ続きが書かれるかの方が問題
11: ニュースソース検討中@自治議論スレ 2018/10/25(木) 13:59:13.30 ID:07k83X+e
それは数学では解析できないわ
13: ニュースソース検討中@自治議論スレ 2018/10/25(木) 14:06:27.91 ID:f3Ul8MUW
やっぱり、欲ってのは人間が動く原動力なんだと思った。
15: ニュースソース検討中@自治議論スレ 2018/10/25(木) 14:27:42.87 ID:bZ/6KaOx
知的なことをしてるな
19: ニュースソース検討中@自治議論スレ 2018/10/25(木) 14:34:55.88 ID:96ol4jeU
バカボンとハジメちゃんが二人で議論してる絵図
20: ニュースソース検討中@自治議論スレ 2018/10/25(木) 14:35:39.62 ID:EXrB+RfJ
>>1

頭の良い奴ほどオタクが多いもんなぁw
33: ニュースソース検討中@自治議論スレ 2018/10/25(木) 14:54:35.99 ID:u/fJKpkD
中学校の確率だったかで組み合わせ問題の初歩は教わったはずだけど、
14個の要素の組み合わせに関しても、まだまだ研究する要素があるんだな。
40: ニュースソース検討中@自治議論スレ 2018/10/25(木) 15:16:14.11 ID:lwfysPWv
ちょっと!
何、言ってんだか解りません?
44: ニュースソース検討中@自治議論スレ 2018/10/25(木) 15:25:24.93 ID:u/fJKpkD
>>40
元記事読むと、この手の羅列が最小置換というらしい。
下記の例だと3種類がもとになっているけど、もとの種類が何種類だと最小置換が何文字になるか、
という定式はなかった。今回、どういう方法か知らんけど、その番組の話数=14種類の組み合わせ
を最小置換した場合、何文字になるかが判明した。

https://i.gzn.jp/img/2018/10/25/suzumiya-haruhi-superpermutation/abcabacba_m.jpg

BAAB佐竹も最小置換
43: ニュースソース検討中@自治議論スレ 2018/10/25(木) 15:24:39.53 ID:QJv7IPt3
           ,. - ── - 、
       r'つ)∠───    ヽ
      〆⌒  ̄ ̄ ̄ \__r 、  \
     ,.イ      ,イ    \ヽ,\rv-,
    ヾイ    /{ { ヽ、ト、  \Y <ノノ\
    {  .ト{\ヽ',  メ __\  } ⌒ヽ }へ
     ゝ  |"ひ)  \  イびゞ \ ヽ- 、ノ   // >=
     ノ  ト、"´,.     ー ノ ///\/ /    \
    /.  {   ゝ     /  レ//  } Y´      \
    {   ヽ  ヽ⌒>  /    レ´TTア⌒>、_    \
    V{   \ └ ´  / ,.イ/  /ll |   /≦__    }
      V{   >ー┬|/  ! ,.イノ || |  /   ̄ ̄ ̄  /
       リヽイ|   /:| l _|' '´  || |  |     _/
        /{{ |   |===|    || |   __/
123: ニュースソース検討中@自治議論スレ 2018/10/27(土) 12:07:13.80 ID:MBXXJcKQ
>>43
懐かしの涼宮ハルピンw
45: ニュースソース検討中@自治議論スレ 2018/10/25(木) 15:25:51.17 ID:aK4B6Ul0
長門「その内わかる」
52: ニュースソース検討中@自治議論スレ 2018/10/25(木) 16:29:31.86 ID:rotND09I
ABBA
69: ニュースソース検討中@自治議論スレ 2018/10/25(木) 19:12:35.90 ID:sNcvvvbn
ふ~ん
オタクも役に立つことあるんだ
71: ニュースソース検討中@自治議論スレ 2018/10/25(木) 19:29:54.03 ID:8CExX42S
何言ってるか全然分からない
「上から読んでも下から読んでも山本山」みたいな話か?
74: ニュースソース検討中@自治議論スレ 2018/10/25(木) 19:47:22.56 ID:2a1WA+tJ
>>71
その順番にDVDを並べておけば
自分の見たい順番に並んでる部分が必ずあるってこと

DVD14巻をこの答えの順番に939億枚並べておけば
誰でも自分の好きな順番に14枚が並んでる部分が必ずある。
80: ニュースソース検討中@自治議論スレ 2018/10/25(木) 20:34:38.46 ID:bJyYgqPp
>>74
問題は939億から自分の好きな順番で並んでいる箇所をどうやって見付けるのか
88: ニュースソース検討中@自治議論スレ 2018/10/25(木) 22:09:06.81 ID:dm/9aAZ7
>>80
そこが数学の物足りなさだよな
全体として必ずあることは間違いなく証明するけど
じゃあどこにあるのか、までは明示できない
101: ニュースソース検討中@自治議論スレ 2018/10/26(金) 06:25:40.90 ID:CwQaxJaT
>>88
最小置換文字列数問題は未だ証明されてないはず。
そして、最小置換文字列が線形処理で作れるとして、
その「どこ」に目的の組み合わせがあるかも課題と
なっている。それが判明すれば、それも数学が世界
に誇れる貢献のなるよ。

だって長大データの検索システムはいまだ数学的に
最高効率でデータ検索できるようにはなってないから
癖のある近似ロジックで対応してるんだから。
97: ニュースソース検討中@自治議論スレ 2018/10/26(金) 00:56:00.24 ID:VQb1OqBr
BABじゃだめなの?
102: ニュースソース検討中@自治議論スレ 2018/10/26(金) 07:57:21.98 ID:ip8a1jDr
>>97
正解には全ての順列が現れているので、正解の文字を入れ換えても全ての順列が現れる。つまり、正解であるABAの文字を入れ換えたBABも正解になる。
103: ニュースソース検討中@自治議論スレ 2018/10/26(金) 10:46:01.96 ID:VQb1OqBr
>>102
そういうことか。
現れる「順序」は関係ないってことね
129: ニュースソース検討中@自治議論スレ 2018/10/27(土) 16:32:07.78 ID:dmmY5Zqk
PPAPは何を内包してるの?