「最小超置換問題／ハルヒ問題」の編集履歴（バックアップ）一覧に戻る
最小超置換問題／ハルヒ問題 - (2025/06/09 (月) 09:52:35) のソース
&font(#6495ED){登録日}：2025/02/22 Sat 19:24:15
&font(#6495ED){更新日}：&update(format=Y/m/d D H:i:s) &new3(time=24,show=NEW!,color=red)
&font(#6495ED){所要時間}：約 4 分で読めます
----
&link_anchor(メニュー){▽}タグ一覧
&tags()
----
&b(){最小超置換問題(The minimal superpermutation problem)}とは、数学における未解決問題の1つである。
本項目では最小超置換問題のバリエーションの1つである&b(){ハルヒ問題(The Haruhi problem)}についても解説する。
●目次
#contents
*最小超置換問題の概要
まずは最小超置換問題についての概要を記す。この問題は以下のような要点でまとめられる。
&font(b,#0000ff){重複しないn記号の文字列について、その最小超置換である順序列の長さはいくらか}
以下では具体例を交えて解説する。
n=3の場合で、重複した文字列のない場合の置換の数を考えてみよう。
これは3!=6通りであることはすぐに分かり、a,b,cの記号を用いれば以下のような6つの順序列である。
abc acb bac bca cab cba
ここでa,b,cの文字を使って、上記6つの順列を全て含む文字列を作り、その文字列の長さ調べてみよう。
単純に上記の文字列を繋ぎあわせれば6つの置換を含む文字列が完成し、その文字列の長さは3×6=18である。
このように元の順列を含む順列を「超置換」と呼ぶ。
ここで、上記順列の1つ目と2つ目繋ぎあわせたabcacbはbcaの組み合わせを含む。
このような場合はbcaを含み省略できると考えると、超置換の長さを短くすることができる。
n=3の場合の最小の超置換の例の1つはabcabacbaとなり、その長さは9となる。
では一般のn文字について、その最小超置換の長さはどのように与えられるだろうか。
この問題は1993年にAshlockとTillotsonによって議論され、その長さは1! + 2! + … n!であると予想された。
この予想はn=1～5の時は正しいのだが、n=6の場合この式が与える値873よりも小さい最小超置換の例872が見つかってしまっている。
よって一般化したnの場合の最小超置換の長さを求める問題は未解決となっている。
*ハルヒ問題の概要
ハルヒ問題とは、『[[涼宮ハルヒの憂鬱]]』に関連する問題である。
2006年のテレビアニメ版『涼宮ハルヒの憂鬱』は全14話が放送されたが、放送順は原作順とも時系列順とも異なっていた。
原作から知っている視聴者でも楽しめるような構成である。
そんな『ハルヒ』のアニメであるが、2011年に英語圏最大の匿名掲示板4chanの科学・数学板で第1期アニメについて次のような議論がされていた。
&font(b,#0000ff){14エピソードを全ての組合せの順番で効率よく視聴するには何話見ればいいのか？}
簡単には答えは出なかったのだがそれもそのはず、これはn=14における最小超置換問題に他ならない。
結局直接的な答えは出なかったが、一般化したnにおいて少なくともどの程度のエピソードを見る必要があるかを提示した「名無しさん」が現れる。
彼によれば以下で表される式により、視聴数の下限が求まるという。((この式は最小超置換の長さそのものではなく、その値の範囲を下限として示したものであることに注意。))
n! + (n−1)! + (n−2)! + n − 3
スレ内においてはその後も活発な議論がなされていたようだが、結局精査はされずにネットの海に沈んでしまうのであった。
*最小超置換問題の進展
時は流れて2018年10月。最小超置換の下限に関する議論は活発化する。
数学者・コンピュータ科学者のRobin Houston氏が当時のTwitter上にてこの証明について言及。((正確には、Twitter上で引用したのは世界最大のwikiサービスFandomのハルヒ問題のページ。))
「興味深い状況だ」と関心を示し、同月内に上記の式の証明に関する論文を提出した。
論文の第一筆頭著者は『Anonymous 4chan Poster』、即ち「名無しさん」となっており、アーカイブであるが4chanの該当スレも引用されている((https://oeis.org/A180632/a180632.pdf))。
&font(l){URLの文字列にはwarosuの文字が入っているため、かなりシュール。なにわろてんねん。}
また、同時期には最小超置換の上限に関する式についてGreg Egan氏((数学者であるとともにSF作家でもあり、代表作に『順列都市』がある。アニヲタ的には『バーナード嬢曰く。』のSFオタク神林しおりが特に愛読する作家として有名か。))が証明。
最小超置換の上限の数は多くともn! + (n−1)! + (n−2)! + (n−3)! + n − 3であることが示された。
これにより最小超置換の長さの範囲が絞られたことになるが、具体的な式の導出には至っておらず未解決のままとなっている。
*余談
・本家[[Wikipedia]]の英文ページ『Superpermutation』では、超置換の下限に関する項でハルヒ問題についても詳しく紹介されている。&br()&font(l){一方で、和文ページでは匿名投稿者が発見した程度にとどまっている。}
・最小超置換の下限・上限の式により、14話の組み合わせを全て視聴するには&b(){少なくとも93,884,313,611話}、&b(){多くとも93,924,230,411話}見る必要がある。&br()約939億話であり、1話を24分とすると&b(){約430万年の時間}が必要になる。
・単純に14話の置換を繋げた超置換の長さは14×14!≒1兆2200億である。&br()最小超置換の順番で見れば&b(){90%以上も効率的に視聴することができる}ことがわかる。
追記・修正は最小超置換問題を解いてからお願いします。
#include(テンプレ２)
#right(){この項目が面白かったなら……＼ポチッと/
#vote3(time=600,5)
}
#include(テンプレ3)
#openclose(show=▷ コメント欄){
#areaedit()
- 何やこれ…「何故か立ってしまった項目」のタグもいるかな？ -- 名無しさん (2025-02-22 20:19:23)
- >14エピソードを全ての組合せの順番で効率よく視聴するには何話見ればいいのか？ お前は何を言っているんだ -- 名無しさん (2025-02-22 21:11:59)
- 結構有名な話が出てきたな。主婦や職人が証明や新発見をすることもあるし、数学の世界はあらゆる相手に広がっていると実感するわ -- 名無しさん (2025-02-22 21:59:35)
- 正直、「何故か立ってしまった～」云々のタグって、作成者に失礼な気がするけどね。違反項目でない限り何を立ててもいいのに -- 名無しさん (2025-02-22 22:02:19)
- なんならハルヒというアニヲタwikiおあつらえ向きのネタまで備えてるのだからむしろ立ってなかったのが不思議なぐらい -- 名無しさん (2025-02-22 23:41:40)
- グレッグ・イーガンってあのグレッグ・イーガンなのか 順列都市とか書いてるしちょっと考えると納得だけど -- 名無しさん (2025-02-22 23:51:32)
- 「効率よく」ってのは「同じ話を2話連続で見ずに」ってことね？ -- 名無しさん (2025-02-23 00:52:54)
- 「効率よく」てのは、「全てのパターンを最小の回数で見る」ってこと。本文中のabcの例だと、3文字の組み合わせ6通りである18文字を、9文字の文字列で表現できる。 -- 名無しさん (2025-02-23 04:53:59)
- つまりハルヒのアニメを順番に流していって「この話の伏線があの話で回収される！」を最大効率で見れて気持ちいい～組み合わせこそ『最小超置換』と呼べる。って事 まぁんなもん探し当てるには記事通り430万年要るだろうし 一話から見てもハルヒは面白いよ -- 名無しさん (2025-02-24 04:05:18)
- 一般人は普通につながるように再編すればいいやん、ってなるからこの話がまったく理解できない。 -- 名無しさん (2025-02-24 06:18:04)
- アニメハルヒの時系列シャッフル放送が評価されたのは放送後であって、放送中はワケわからんと不評を買ってたのを覚えてる。 -- 名無しさん (2025-02-25 00:12:54)
- この問題が解決すればイグノーベル賞取れそう -- 名無しさん (2025-02-26 08:49:18)
#comment()
#areaedit(end)
}
