<ruby><rb data-id="template-ruby"><span lang="zh-hant">涼宮春日問題</span><span class="template-ruby-hidden">（</span></rb><rt style="font-size:0.75em"><span lang="zh-hant">最小超置換問題</span></rt><span class="template-ruby-hidden">）</span></ruby>
| |
| 基本資料 | |
| 用語名稱 | The Haruhi Problem （ハルヒ問題； 春日問題；涼宮春日問題） |
|---|---|
| 其他表述 | The Minimal Superpermutation Problem （最小超置換問題； 最小超置換問題） |
| 相關條目 | 涼宮春日的憂鬱、亂序播放、涼宮春日 |
涼宮春日問題（The Haruhi Problem；春日問題；ハルヒ問題）[1][2]，數學界通稱最小超置換問題（The Minimal Superpermutation Problem；最小超置換問題）[3]是一個組合計數難題，原型（如圖）表述為：
| “ | What is the least number of Haruhi episodes that you would have to watch in order to see the original 14 episodes in every order possible? | ” |
| “ | 如想以所有可能的順序看涼宮春日初版14話動畫則最少要看多少話？ | ” |
推廣後的一種抽象數學表述為：
| “ | What is the minimum length of a string of symbols that contains every permutation of n symbols? | ” |
| “ | 包含n種字符全部置換的字符串其最小長度為何？ | ” |
ACG背景
《涼宮春日的憂鬱》共拍攝了2006與2009兩個版本的TV動畫，其中初版（06版）首播為亂序播放，共14話。其TV播放順序與故事的時間軸順序，以及後來的DVD版收錄順序均不相同。
| 話數 | 日文標題 | 中文標題 | 首播時間 | ||
|---|---|---|---|---|---|
| 播放順序 | 故事順序 | DVD收錄順序 | |||
| 01 | 11 | 01 | 朝比奈ミクルの冒険 Episode00 | 朝比奈實玖瑠的冒險 Episode00 | 2006年4月2日 |
| 02 | 01 | 02 | 涼宮ハルヒの憂鬱I | 涼宮春日的憂鬱 Ⅰ | 2006年4月9日 |
| 03 | 02 | 03 | 涼宮ハルヒの憂鬱II | 涼宮春日的憂鬱 Ⅱ | 2006年4月16日 |
| 05 | 03 | 04 | 涼宮ハルヒの憂鬱III | 涼宮春日的憂鬱 Ⅲ | 2006年4月30日 |
| 10 | 04 | 05 | 涼宮ハルヒの憂鬱IV | 涼宮春日的憂鬱 Ⅳ | 2006年6月4日 |
| 13 | 05 | 06 | 涼宮ハルヒの憂鬱V | 涼宮春日的憂鬱 Ⅴ | 2006年6月25日 |
| 14 | 06 | 07 | 涼宮ハルヒの憂鬱VI | 涼宮春日的憂鬱 Ⅵ | 2006年7月2日 |
| 04 | 07 | 08 | 涼宮ハルヒの退屈 | 涼宮春日的煩悶 | 2006年4月23日 |
| 07 | 08 | 09 | ミステリックサイン | 神秘信號 | 2006年5月14日 |
| 06 | 09 | 10 | 孤島症候群(前編) | 孤島症候群（前篇） | 2006年5月7日 |
| 08 | 10 | 11 | 孤島症候群(後編) | 孤島症候群（後篇） | 2006年5月21日 |
| 12 | 12 | 12 | ライブアライブ | Live Alive | 2006年6月18日 |
| 11 | 13 | 13 | 射手座の日 | 射手座之日 | 2006年6月11日 |
| 09 | 14 | 14 | サムデイ イン ザ レイン | Someday in the Rain | 2006年5月28日 |
數學背景
定義n個字符的超置換（superpermutation）為其子串包含所有n個字符的置換的字符串，則春日問題等價於尋找n個字符最小超置換的長度。
例如，當1 ≤ n ≤ 5時，最小置換的長度為 1! + 2! + … + n! ，對應的超置換為1, 121, 123121321, 123412314231243121342132413214321, 以及
123451234152341253412354123145231425314235142315423124531243 512431524312543121345213425134215342135421324513241532413524 132541321453214352143251432154321
2011年，在著名網絡屎尿屁論壇4chan上，用戶ニア愛 !pQsULI4sXc發佈了包含春日問題原型的改圖（即本條目配圖），意外地引發了嚴肅討論。一位匿名用戶肥肥隨後在論壇推導出了一個n個字符的超置換所至少具有的長度為：
n! + (n-1)! + (n-2)! + n - 3 (n≥2)[4]
這個結果是目前最優（長）的超置換長度下界。
遺憾的是，鄉民的這一成果在當時並未引起數學界的足夠重視。
直到2018年，數學家Robin Houston在推特上公開了上述文獻調研結果時才引起了人們的興趣，他很快與另外兩位數學家一起整理規範了該鄉民張貼的證明過程與結果，以預印本論文形式發表於同年10月25日，文中匿名鄉民被署記為Anonymous 4chan Poster，位列第一作者。[2]
根據該算法，當n=14時，目前下界的最優解為93,884,313,611。
也就是說宅宅們現在至少需要馬拉松式地連續看九百三十八億八千四百三十一萬三千六百一十一集06版涼宮(註)大約需要四百四十萬年，約合七千五百個大萌神的暑期，才有可能欣賞到全部可能的置換方法。
另一方面，目前最優（短）的最小超置換長度上界：
n! + (n-1)! + (n-2)! + (n-3)!+n - 3 (n≥7)[5]
則是由數學家、科幻作家Greg Egan在2018年10月提出的。當n=14時，上界為93,924,230,411。
也就是說宅宅們馬拉松式地以最短方法連續欣賞完06版涼宮全部可能的置換方法，也不會看超過九百三十九億二千四百二十三萬零四百一十一集。
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| |||||||||||||||||||||||||||||||||
註釋與引用
- ↑ /sci/ : The Haruhi Problem
- ↑ 2.0 2.1 A lower bound on the length of the shortest superpattern Anonymous 4chan Poster, Robin Houston, Jay Pantone,Vince Vatter
- ↑ OEIS：A180632
- ↑ . "Permutations Thread III" 4chan：Anonymous(2011年9月17日)
- ↑ Greg Egan：Superpermutations