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


/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通りの組み合わせが内包されています。
no title


また、A・B・Cという3要素の組み合わせは「ABC」「ACB」「BAC」「BCA」「CAB」「CBA」の6通り。そして3文字の最小超置換は「ABCABACBA」という9文字の文字列となります。「ABCABACBA」という文字列には、6通りの組み合わせが全て内包されています。
no title


この最小超置換の文字列の長さは、要素が増えるごとに爆発的に増えると考えられています。記事作成時点では、最小超置換の文字数は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/
3: ニュースソース検討中@自治議論スレ 2018/10/25(木) 13:32:18.57 ID:SGoLf7Pn
ハルヒが世界を変えた

15: ニュースソース検討中@自治議論スレ 2018/10/25(木) 14:27:42.87 ID:bZ/6KaOx
知的なことをしてるな

9: ニュースソース検討中@自治議論スレ 2018/10/25(木) 13:43:32.66 ID:IwHIlelt
何のこと言っとるか全くわからんがw(^o^)
ず~~~っと考えていたことが「涼宮ハルヒ」を見ていたら
わかったということかwww

よかったねw

4: ニュースソース検討中@自治議論スレ 2018/10/25(木) 13:37:35.41 ID:Ez6FBj6c
途中で寝てしまった!!

6: ニュースソース検討中@自治議論スレ 2018/10/25(木) 13:39:41.26 ID:Kg11SWgE
そもそもどういう構成なのかわからん

68: ニュースソース検討中@自治議論スレ 2018/10/25(木) 19:12:33.73 ID:vnfTnTT9
ハルヒを観る順番となんの関係もないじゃん

49: ニュースソース検討中@自治議論スレ 2018/10/25(木) 15:59:26.58 ID:GmBZxem3
>少なくとも939億2423万411話のエピソードを見る必要があるとのこと

数学者ってのは現実を無視したキチガイだからなw
普通に全話見て、頭の中で好きなように置き代えるのが人間ってもんだw

53: ニュースソース検討中@自治議論スレ 2018/10/25(木) 16:40:58.12 ID:vwApGaFp
>>49
だれも好きなように置き換える総数の話なんてしていない

40: ニュースソース検討中@自治議論スレ 2018/10/25(木) 15:16:14.11 ID:lwfysPWv
ちょっと!
何、言ってんだか解りません?

44: ニュースソース検討中@自治議論スレ 2018/10/25(木) 15:25:24.93 ID:u/fJKpkD
>>40
元記事読むと、この手の羅列が最小置換というらしい。
下記の例だと3種類がもとになっているけど、もとの種類が何種類だと最小置換が何文字になるか、
という定式はなかった。今回、どういう方法か知らんけど、その番組の話数=14種類の組み合わせ
を最小置換した場合、何文字になるかが判明した。

no title


BAAB佐竹も最小置換

17: ニュースソース検討中@自治議論スレ 2018/10/25(木) 14:30:11.32 ID:ge4CRO/W
親戚のうちにドラえもん全巻が巻数ばらばらに並んでたのを適当に読んでたのを思い出した

20: ニュースソース検討中@自治議論スレ 2018/10/25(木) 14:35:39.62 ID:EXrB+RfJ
>>1

頭の良い奴ほどオタクが多いもんなぁw

39: ニュースソース検討中@自治議論スレ 2018/10/25(木) 15:08:06.48 ID:UA3Wvm4s
あっちのオタクは消費するだけじゃなく
知的なオタク多いな

33: ニュースソース検討中@自治議論スレ 2018/10/25(木) 14:54:35.99 ID:u/fJKpkD
中学校の確率だったかで組み合わせ問題の初歩は教わったはずだけど、
14個の要素の組み合わせに関しても、まだまだ研究する要素があるんだな。

37: ニュースソース検討中@自治議論スレ 2018/10/25(木) 15:06:30.90 ID:y4i+sckc
解放が発見されそうなことも凄いが、
>「可能な限りの順序で全てのエピソードを見たい場合、最も少ない組み合わせは何通りになるか」という問題が提起
した奴も凄いな。日常生活のすぐ外に未知の世界が広がってると感じさせる良い話。

14: ニュースソース検討中@自治議論スレ 2018/10/25(木) 14:15:40.85 ID:HxRexYAW
最短超文字列問題だろ?

36: ニュースソース検討中@自治議論スレ 2018/10/25(木) 15:06:05.23 ID:ZPdOrp+y
n=14 の場合の解を書き込んだのは何者?
未来からの投稿・実験中のAIによる投稿
……なんて可能性が残ってるとロマンがある。

57: ニュースソース検討中@自治議論スレ 2018/10/25(木) 17:21:32.12 ID:A+DKOvw5
>>36
ペレルマンだという噂がある

グリゴリー・ペレルマン - Wikipedia
グリゴリー・ヤコヴレヴィチ・ペレルマンまたはペレリマン(Григорий Яковлевич Перельман, Grigori Yakovlevich Perelman, 1966年6月13日 – )は、ロシア出身の数学者。
89: ニュースソース検討中@自治議論スレ 2018/10/25(木) 22:10:39.37 ID:8sZ3lQKy
>>57
ペレルマンさん何してはるんですか?って話になる気もしなくもないですが、ちょっとした息抜きでやってみたら思いの外真実に近付いた、みたいな話だったらロマンあるの。

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
最小置換文字列数問題は未だ証明されてないはず。
そして、最小置換文字列が線形処理で作れるとして、
その「どこ」に目的の組み合わせがあるかも課題と
なっている。それが判明すれば、それも数学が世界
に誇れる貢献のなるよ。

だって長大データの検索システムはいまだ数学的に
最高効率でデータ検索できるようにはなってないから
癖のある近似ロジックで対応してるんだから。

106: ニュースソース検討中@自治議論スレ 2018/10/26(金) 12:46:30.86 ID:lm7fwPB4
>>88
組み合わせの数を求める数式とその出現場所を求める数式は異なる
そこが君の頭の足りなさだな

92: ニュースソース検討中@自治議論スレ 2018/10/25(木) 22:59:04.74 ID:WMsWtE6k
>>74
だからそれがハルヒと何の関係があるんだよ

99: ニュースソース検討中@自治議論スレ 2018/10/26(金) 02:24:28.41 ID:UluFqOGT
>>92
ハルヒは放送順とシナリオの時系列が一致しないから、どの順番で見るべきか議論があるらしい

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
そういうことか。
現れる「順序」は関係ないってことね

91: ニュースソース検討中@自治議論スレ 2018/10/25(木) 22:34:35.03 ID:VjNMTwr5
このアニメ、何でこんなに有名になったんだろうね?

84: ニュースソース検討中@自治議論スレ 2018/10/25(木) 21:30:11.24 ID:Oj09u05v
あれってハルヒとキョンのキスシーンを最終回に持ってきたかったから
あの順番にしただけだよな

73: ニュースソース検討中@自治議論スレ 2018/10/25(木) 19:45:12.83 ID:2a1WA+tJ
猿にタイプライタを打たせたら、いつか必ずシェイクスピアが生まれる
って奴に似てるのかな

13: ニュースソース検討中@自治議論スレ 2018/10/25(木) 14:06:27.91 ID:f3Ul8MUW
やっぱり、欲ってのは人間が動く原動力なんだと思った。


転載元:https://egg.5ch.net/test/read.cgi/scienceplus/1540441618/
このエントリーをはてなブックマークに追加

人気記事ランキング

    おすすめ記事(外部)

     

    コメント

    コメントフォーム
    評価する
    • 1
    • 2
    • 3
    • 4
    • 5
    • リセット
    • 1
    • 2
    • 3
    • 4
    • 5
    • リセット