「ハルヒ問題（Haruhi Problem）」と呼ばれる数学の分野である組合せ論における未解決問題について説明しています。
ハルヒ問題は、アニメ「涼宮ハルヒの憂鬱」のエピソードを可能な全ての順序で視聴するために必要な最小視聴回数を問うことから名付けられました。
この問題は最小超置換問題として知られる数学の難問に相当し、超置換と呼ばれる全ての置換を部分文字列として含む最短の文字列の長さを求めることを目指します。
2011年に匿名投稿によって下限の証明が提示され、2018年にはグレッグ・イーガンによって上限が示されるなど、現在も活発な研究が進められています。
「ハルヒ問題」って何？アニメ好きと数学者がざわついた意外な関係
アニメ「涼宮ハルヒの憂鬱」って、放送順が時系列と違ってて話題になったじゃないですか。
あれをどういう順番で見たら一番楽しめるか？みたいな議論、ファン同士で盛り上がりましたよね。
まさか、あの話題が数学の超難問と繋がってたって知ってますか？
今回紹介するのは、その名も「ハルヒ問題」。
アニメファンはもちろん、数学アレルギーの人でもきっと「へぇ！」ってなる、めちゃくちゃ面白い話なんですよ。
ハルヒ問題｜アニメの視聴順から生まれた数学の問題？
「ハルヒ問題」っていうのは、文字通りあのアニメ「涼宮ハルヒの憂鬱」に由来する名前なんです。
アニメの第1期って全14話だったんですけど、放送された順番が独特でしたよね。
だからこそ、「全ての組み合わせの順番で見てみたいけど、一番効率よく見るにはどうしたらいいの？」っていう素朴な疑問がアニメファンの間で生まれたんです。
この「考えられる全てのエピソードの順序で連続して視聴する時に、最低限見なければいけない視聴回数はいくつか？」という問題こそが、後に「ハルヒ問題」と呼ばれるようになりました。
最初は単なるアニメファンの雑談だったのかもしれません。
それが、英語圏の巨大掲示板「4chan」なんかで議論されてるうちに、数学好きの目に留まって、本格的な数学の問題として扱われるようになったんです。
ハルヒ問題｜たとえば3話だったら？具体例で見てみよう
問題だけ聞くとピンとこないかもしれませんよね。
例えば、エピソードが3話だけだったとしましょう。
この3話を並び替える順番、つまり「置換」は全部で3の階乗、つまり6通りあります。
123、132、213、231、312、321、この6パターンですね。
これらの全ての順番を、できるだけ短い回数見ることで網羅したいんです。
ただ単に6パターンを繋げると、3話×6パターンで18話になります。
でも、これって無駄が多いと思いませんか？
例えば、「123」の次に「231」を見たい場合、ただ繋げると「123231」って6話見ることになります。
でも、「123」の末尾と「231」の先頭って「23」で重なってますよね。
なので、「1231」って見れば、「123」と「231」の両方を含んでいることになるんです。
このように、視聴するエピソードを重ね合わせながら、全ての「あり得る順番」を網羅するんです。
で、最も短い視聴回数で全てを網羅した並び方を「最小超置換」と呼びます。
3話の場合の最小超置換の一つが「123121321」という並び方で、その長さは9なんです。
この「123121321」という並びの中に、さっき挙げた6つの順番（123、132、213、231、312、321）が全て連続した部分として含まれています。
単純に繋げた18話と比べると、半分にまで短縮できてますよね。
ハルヒ問題｜ハルヒ本編14話だとどうなる？
さて、これがハルヒ本編の14話となるとどうなるでしょう？
14話のあり得る視聴順序の組み合わせは、14の階乗（14!）で計算できます。
その数、なんと約872億通り！ マジかよって思いますよね。
これ、単純に872億通りの並び方を全部繋げて見ると、14話×872億で1兆2千200億エピソードも見なきゃいけません。
考えるだけで気が遠くなります。
じゃあ、最小超置換の考え方を使って一番短い視聴回数で見る場合、最低何話必要なんでしょうか？
これに関しては、後述する数学的な進展で「これよりは短くならないよ」という下限の値が示されています。
その計算式で14話を当てはめると、最低でも約939億エピソードは必要になることが分かっています。
これも一生かかっても見きれない数字ですよね。
それでも、単純に全部繋げるより90%以上も効率的になるってんだから、最小超置換を求めることってすごい意味があるんです。
ハルヒ問題｜これって数学の超難問だった！「最小超置換問題」
そうなんです、「ハルヒ問題」としてアニメファンから生まれたこの疑問、実は数学の世界で「最小超置換問題（Minimal Superpermutation Problem）」と呼ばれている超有名な難問だったんです。
この問題は、1993年には既に数学者によって提起されていたんですが、長年、正確な最小の長さを見つけることができていませんでした。
特にnが大きくなるにつれて、その計算や証明はめちゃくちゃ難しくなるんですね。
だから数学者たちは、正確な値を求めるのが難しい時には、せめて「これよりは小さくならない」という下限と、「これよりは大きくならない」という上限を示すことで、少しずつ真の値に迫っていく、という戦略を取ります。
まさに、この最小超置換問題も、長い間、より良い下限や上限を探る研究が続いていたんです。
ハルヒ問題｜解決への意外すぎるきっかけは「匿名掲示板」
そんな長年未解決だった難問に、まさかの突破口が開かれるんです。
それも、きっかけとなったのは2011年、あの「4chan」の科学・数学板への匿名の書き込みでした。
この「名無しさん」が、「最小超置換の長さには、これより短くならない境界（下限）があるはずだ」と、その証明らしきものを投稿したんです。
しかも、その証明を考えるヒントになったのが、まさに「涼宮ハルヒの憂鬱」のエピソード視聴順問題だったというから驚きです。
でも、残念ながらというか、やはりというか、匿名掲示板の書き込みはすぐに数学者のコミュニティで精査されることもなく、時は流れていきました。
せっかくの発見が、ネットの片隅に埋もれそうになってたんですね。
ハルヒ問題｜世界が注目！SF作家も巻き込んだ2018年の進展
状況が大きく動いたのは、それから7年後の2018年10月のことでした。
SF作家としても有名なグレッグ・イーガン氏が、この最小超置換問題に関する新しい発見（より良い上界）をTwitterで発表したんです。彼は数学も専攻していたそうで、こういう問題にも詳しかったんですね。
このイーガン氏の発表をきっかけに、数学者やコンピューター科学者の間でこの問題への関心が再び高まりました。
そして、埋もれていた2011年の4chanの匿名投稿が掘り起こされ、数学者たちによって丁寧に検証されたんです。
その結果、匿名投稿者の示した下界の証明が正しいことが確認されました。
最終的に、この証明は数学者たちの手で論文としてまとめられ、なんと筆頭著者には「Anonymous 4chan Poster（匿名4chan投稿者）」と記されたんです。これ、すごくないですか？
匿名のオタクの雑談から生まれた疑問が、数学の難問に光を当てて、その匿名投稿がまさか論文の筆頭著者になるなんて、ドラマチックすぎますよね。
この一連の流れは、国内外のニュースサイトでも大きく取り上げられて話題になりました。
結局、ハルヒ問題は解決したの？今の状況
じゃあ、結局ハルヒ問題（最小超置換問題）は完全に解決したのかというと…残念ながら、そうではないんです。
匿名投稿者が下界（これより短くならない値）を、グレッグ・イーガン氏がより良い上界（これより長くならない値）を示しましたが、正確な最小超置換の長さはまだ特定されていません。
下界の式は n! + (n-1)! + (n-2)! + n-3。
上界の式の一つは n! + (n-1)! + (n-2)! + (n-3)! + n-3 です。
特にnが6以上の場合は、最小の長さがこれらの式の間に存在することは分かっているんですが、ぴったりの値が何なのかはまだ誰も証明できていないんです。
例えば、ハルヒの14話の場合、下限は約939億話ですが、イーガン氏が示した上限は約939億2400万話くらいになります。
この間の、約2400万話の差の中に、本当の最小の長さがあるはずなんです。
現在も、世界中の数学者がこの「最小超置換問題」に取り組んでいて、より良い上界や下界を見つけたり、最終的な答えを探したりする研究が続いています。
ちなみに、この問題、「巡回セールスマン問題」っていう有名な難問とも関係があるらしいですよ。数学って色々な問題が繋がってるんですね。
ハルヒ問題｜アニメと数学、思わぬコラボ？
いやー、それにしても、アニメ好きのふとした疑問が、長年未解決だった数学の難問に光を当てるきっかけになるなんて、本当に面白い話ですよね。
オタクの情熱が世界を変える、なんてちょっと大げさかもしれませんが、こういう思わぬところから新しい発見が生まれるのが、学問の面白さなのかもしれません。
ハルヒを見ていた人も、そうでない人も、この「ハルヒ問題」を知ることで、ちょっとだけ数学に興味を持ってもらえたら嬉しいです。
もしかしたら、いつかあなたも身近な疑問から、とんでもない大発見をするかもしれませんよ！
