自分、人間向いてないんで

社会不適合者の人生消化試合系日記

ハルヒ問題

f:id:Slumberer:20181029224214j:plain

私はアスペで他人に物事を伝えるのが不得手なので「何言ってだこいつ」となったら牧瀬プリンでも食べながら他のサイトを見ることを勧める。あと間違ってたらごめん。

ハルヒ問題は上の画像の通り、ハルヒ1期14話全てを任意の可能な順番全てで見るとき、最小となるのは何話か?という問題。つまり1~14を並び替えたとき、それらの任意の順列を全て含む列の最小の長さはいくつか?ということ。ハルヒ問題は最小超置換問題でn=14としたときである。これは25年間未解決らしい。

まず置換って何ぞ?という話だが、雑にいうとアナグラムである。要はただ順番を入れ換えるだけ。たとえば3個の数字の集合{1,2,3}の置換は全部でS3={e,(12),(13),(23),(123),(132)}の6個である(PCで添え字とかの書き方分からないので見にくいかもしれない)。e(恒等置換)は順番はそのまま変えない、(123)は1があった場所に2、2があった場所に3、3があった場所に1が来るように並び替えますよという意味。もちろん順番が合ってれば好きにして良いので(123)は(231)or(312)とも表せる。

いきなりnとしても意味不明なので小さい数で考えると、n=1のときは1、n=2のとき121であり、さっきのn=3のときは123121321の9個が最小である。これは実際1,2,3を並び替えて出来る全ての数123,132,213,231,312,321の並びを含む(123はe,132は(23),213は(12),・・・(ryに対応)。ハルヒ問題を解くには同じことを14でやれば良い・・・のだが実際にやるととんでもなく長くなり93,924,230,411話になる。まあ900億超えるらしい。1話24分とすると1日24時間通して見続けても4288777年かかることになる。長門でもキレそう。

詳細は上にも貼ったリンクとそれを元にした数学者Jay Pantone氏の論文に載っているのでまあそっち見た方が良いかと。とりあえずエンドレスエイトよりやばいっぽい。