自古評論出人才，這不澳大利亞科幻作家格雷格·伊根(Greg Egan)提出的一項新證明，以及2011年匿名發(fā)布在網(wǎng)上的新證明被科學(xué)家譽(yù)為是解決一個至少有25年研究歷史的謎題的重大突破口。2011年9月16日一位動漫迷在網(wǎng)上布告欄4chan上發(fā)布了一個關(guān)于狂熱崇拜宗教經(jīng)典電視劇《Haruhi Suzumiya》的數(shù)學(xué)問題。第一季的節(jié)目，包括時間旅行，最初以非時間順序播出，重播和DVD版本的每進(jìn)一步都重新安排片段。粉絲們正在網(wǎng)上討論觀看這些劇集的最佳順序，4chan的發(fā)布者想知道：如果觀眾想以各種可能的順序觀看該劇，他們觀看的最短劇集列表是怎樣的？

博科園-科學(xué)科普：在不到一小時的時間里，一位匿名的人給出了一個答案，這個解決方案算不上完整，并且需要劇集數(shù)量的下限。這場爭論涵蓋了任意數(shù)量的劇集，匿名者表明，對于《Haruhi Suzumiya》第四季的14集來說，觀眾至少要看938.84313611億個片段才能看到所有可能出現(xiàn)的排序，這位匿名發(fā)帖者寫道：請仔細(xì)檢查證明過程，看看我是否漏掉了什么重要信息”。匿名者的證明在數(shù)學(xué)學(xué)界被埋藏了7年之久，雖然當(dāng)時有一位專業(yè)數(shù)學(xué)家發(fā)現(xiàn)了它，但他卻沒有仔細(xì)檢查證明過程。在上個月，澳大利亞科幻小說家格雷格·伊根的發(fā)現(xiàn)重新激起了人們對這個問題的興趣，并引起了人們對2011年匿名發(fā)布的下限問題的關(guān)注。

數(shù)學(xué)家們很快驗證了伊根的上界和下界一樣，適用于任何長度的級數(shù)。隨后，數(shù)據(jù)可視化公司Kiln的數(shù)學(xué)家羅賓?休斯頓(Robin Houston)和密爾沃基馬凱特大學(xué)(Marquette University)的杰伊?潘通(Jay Pantone)獨立證明了4chan匿名發(fā)布者的計算結(jié)果：我們花了很多功夫才弄清楚它是否正確。現(xiàn)在休斯頓和潘通，以及位于蓋恩斯維爾的佛羅里達(dá)大學(xué)的文斯·瓦特斯，已經(jīng)寫了正式的論點。在論文中，他們將第一作者列為“匿名4chan的發(fā)布者”。是一種很奇怪的情況，如此簡練的證明竟被張貼在如此不為人知的地方。

1、排列城市

如果一部電視劇只有三集，那么觀眾可以選擇六種觀看順序：123、132、213、231、312和321。你可以把這六個序列串在一起，得到一個18集的列表。雖然其中包含了所有的排序，但是123121321這樣的排序方法更為有效，這樣一個序列包含了n個符號集合的所有可能重排(或排列)，被稱為“超排列”。在1993年，丹尼爾·阿什洛克 和詹尼特·蒂洛森發(fā)現(xiàn)，如果觀察不同n值的最短超排列，很快就會發(fā)現(xiàn)一個包含階乘的模式——那些用n表示的數(shù)字！這涉及到將所有的數(shù)字相乘直到n：例如，4!= 4×3×2×1。如果系列只有一集，那么最短的超排列長度是1!(也被稱為plain old 1)對于兩集的電視劇，最短的超排列長度是2!+ 1 !；對于三集長度是3集!+ 2 !+ 1 !；四集是4!+ 3 !+ 2 !+ 1 !。

超級排列的階乘規(guī)則成為了傳統(tǒng)智慧(盡管沒有人能證明它對應(yīng)的每個n值都正確)，數(shù)學(xué)家后來在n = 5時證實了這一點。2014年休斯頓讓數(shù)學(xué)家們震驚地發(fā)現(xiàn)當(dāng)n = 6時，這一模式就走向崩潰。階乘規(guī)則預(yù)測，每一種順序看6集需要873個片段，但休斯頓在872處找到了一種方法，可以將n個符號上的超置換變換轉(zhuǎn)換成n + 1個符號上的超置換變換，休斯頓的方法意味著階乘規(guī)則對n以上的每一個值都失效。休斯頓的建筑工作是將超級排列問題轉(zhuǎn)化為著名的旅行推銷員問題——尋找穿過一系列城市的最短路線。更具體地說，超級排列與“不對稱”的旅行推銷員問題有關(guān)，在這個問題中，兩個城市之間的每條路徑都有成本(兩個方向不一定相同)，所以就要找到貫穿所有城市的最便宜的路線。

這種轉(zhuǎn)換非常簡單:把每個排列想象成一個“城市”，想象從一個排列到另一個排列的路徑。在超級排列問題中，想要列出所有排列可能的最短數(shù)字序列，就要通過在開始排列時增加盡可能少的數(shù)字來進(jìn)行排列。因此每條路徑的代價就是我們要在第一個排列的末尾附加位數(shù)來得到第二個排列。例如在n = 3的例子中，從231到312的路徑花費1美元，因為我們只需要在231的末尾加一個2就能得到312，而從231到132的路徑花費2美元，因為我們必須加一個32。通過這種設(shè)置，通過城市最便宜的路徑直接對應(yīng)于最短的超級排列。

這種轉(zhuǎn)換意味著休斯敦可以把旅行商算法的能力轉(zhuǎn)化為超排列問題。旅行商問題是一個NP-hard問題，意思是沒有有效的算法可以解決它的所有情況。但是，有一些算法可以有效地解決一些情況，以及其他算法產(chǎn)生良好的近似解。休斯敦使用后者中的一個來產(chǎn)生他的872位超排列。因為他只給出了一個近似解，所以它可能不是最好的超置換，數(shù)學(xué)家們正在用巨大的計算機(jī)搜索六個符號中最短的超排列。我們知道的搜尋將在有限時間內(nèi)完成，但不知道是一周還是100萬年。

2、錯誤的命令

到休斯敦開始研究時，匿名的4Chan-Press已經(jīng)在互聯(lián)網(wǎng)角落里等待了將近三年。山埃里森大學(xué)的數(shù)學(xué)家納撒尼爾·約翰斯頓，在帖子發(fā)布幾天后，在另一個網(wǎng)站上注意到了一份復(fù)制品，注意到這份帖子不是因為他是動畫迷，而是因為他在Google中輸入了一系列與超級排列相關(guān)的搜索詞。約翰斯頓讀了這個論點之后認(rèn)為它有一定的合理性，但沒有投入太多精力仔細(xì)檢查它。當(dāng)時數(shù)學(xué)家們認(rèn)為超級排列的階乘公式可能正確，當(dāng)你認(rèn)為你知道一個問題的確切答案時，下界這一條件并不引人注意。換句話說，超級排列研究的插曲不合順序。約翰斯頓后來在幾個網(wǎng)站上提到了下界，但休斯頓說：我認(rèn)為沒有人會特別注意它。

今年9月26日加州大學(xué)河濱分校(University of California, Riverside)數(shù)學(xué)家約翰·貝茲(John Baez)在Twitter上發(fā)布了一篇關(guān)于休斯頓2014年發(fā)現(xiàn)的文章，并引起了伊根的注意。幾十年前，伊根還是數(shù)學(xué)專業(yè)的學(xué)生，在那之前，他以科幻小說家的身份開創(chuàng)了一份屢獲殊榮的職業(yè)，我從未停止過對數(shù)學(xué)的興趣。伊根想知道是否有可能構(gòu)建比休斯頓更短的超級排列。他在文獻(xiàn)中尋找關(guān)于如何通過排列網(wǎng)絡(luò)構(gòu)建短路徑的論文，幾周后他就找到了他需要的東西。一兩天之內(nèi)，就提出了一個新的上限，即n個符號的最短超排列的長度:n!+ (n - 1)!+ (n - 2)!+ (n - 3)!+ n - 3。它類似于舊的階乘公式，但是項數(shù)變少了，它絕對打破了以前的上限。與此同時4chan匿名的發(fā)布者的下界與新上界驚人地接近:n!+ (n - 1)!+ (n - 2)!+ n - 3。

當(dāng)Egan的結(jié)果公開后，約翰斯頓提醒其他數(shù)學(xué)家關(guān)注匿名發(fā)布者的證明，而休斯敦和潘通很快證明了它是正確的。引用休斯頓的轉(zhuǎn)換思維：下界顯示的路線通過所有的城市必須沿著一些最低成本的路徑數(shù)量超過1美元，而每個n的上界構(gòu)造特定的路線，只使用1美元和2美元連接。研究人員現(xiàn)在正試圖將上界和下界結(jié)合起來，找到一個解決超排列問題的單一公式。貝茲預(yù)測：也許人們最終會完全解開這個謎團(tuán)，現(xiàn)在看起來不錯。對于Haruhi的粉絲來說，伊根的構(gòu)建給出了明確指導(dǎo)，告訴他們?nèi)绾卧?3,924,230,411片段里觀看第一季所有可能的排序。觀眾可以立即開始狂看，或者等著數(shù)學(xué)家是否能把這個數(shù)字削減下來。匿名發(fā)布者證明了這種縮減不可能拯救超過4000萬片段的劇情，但這足以讓第二季有個不錯的開始。

博科園-科學(xué)科普｜公開論文截圖來自：docs.google

文：Erica Klarreich/Quanta magazine/Quanta Newsletter

博科園-傳遞宇宙科學(xué)之美