圖片來源：Pixabay
網(wǎng)絡(luò)論壇 4chan 以宅文化聞名，然而一個匿名網(wǎng)友多年前發(fā)布的帖子里竟然包含了優(yōu)雅的數(shù)學(xué)證明。最近這條證明被重新發(fā)現(xiàn)，數(shù)學(xué)家們對它進行了驗算，并在最終的論文中將“4chan 匿名網(wǎng)友”列為第一作者。
2011 年 9 月 16 日，一名動漫愛好者在 4chan 上提出了一個數(shù)學(xué)問題，討論動畫《涼宮春日的憂郁》的觀看次序。這部動畫的第一季包含時間旅行劇情，最初以非時間線性順序播出，重播和 DVD 版也都采取了不同的順序。粉絲們在網(wǎng)上交流最佳的觀看順序，而有位 4chan 網(wǎng)友提問：要想以每一種可能的順序觀看這部劇集，那么播放列表的最短長度是多少？
一小時之內(nèi)，有匿名網(wǎng)友提交了答案——這不是一個完整的解答，而是所需的最少劇集數(shù)量的下界（lower bound）。論證中給出了對于任何數(shù)量的劇集的計算方式，并表明對于包含 14 集的《涼宮春日的憂郁》第一季，觀眾需要至少觀看 93,884,313,611 集，才能看到所有可能的順序。“請檢查（證明），看看有沒有什么可能的漏洞，”這個匿名網(wǎng)友寫道。
七年來，這個證明并未進入數(shù)學(xué)界的視線——顯然當(dāng)時只有一名專業(yè)的數(shù)學(xué)家看到了它，而且他沒有仔細檢查。直到上個月，它才迎來了命運的轉(zhuǎn)折點。澳大利亞科幻作家格雷格·伊根（Greg Egan）證明了所需劇集數(shù)量的上界（upper bound），重新引發(fā)了數(shù)學(xué)家對這個問題的興趣，并讓 2011 年那個匿名發(fā)布的下界證明也得到了關(guān)注。這兩個證明都被視為重要的研究進展，為解開一個困擾了數(shù)學(xué)家至少 25 年的問題提供了啟發(fā)。
數(shù)學(xué)家們很快驗證，伊根的上界和匿名網(wǎng)友計算的下界適用于任何長度的集合。數(shù)據(jù)可視化公司 Kiln 的一名數(shù)學(xué)家羅賓·休斯頓（Robin Houston）和馬凱特大學(xué)（Marquette University）的杰伊·潘通（Jay Pantone）分別獨立驗證了 4chan 匿名網(wǎng)友的工作。“要驗證這個證明是對是錯花了不少工夫，”潘通說，因為證明的關(guān)鍵思想并沒有得到特別明確的表達。
如今，休斯頓、潘通和弗羅里達大學(xué)（University of Florida）的文斯·維特（Vince Vatter）共同發(fā)表了一份正式的證明，他們在論文中將“4chan 匿名網(wǎng)友”列為第一作者。
休斯頓說：“如此優(yōu)雅地證明了一個不為人知的問題，而且還出現(xiàn)在這樣一個不太可能的地方，這種情況還真奇怪。”
排列之城
如果一部劇集只有 3 集，那么它有 6 種可能的觀看次序：123、132、213、231、312 和 321。你可以把這六種次序連起來，得到一個長度為 18 集的播放列表，其中包含了所有可能的次序，但還有一種更加高效的方式，就是 123121321（共 9 集）。這樣的序列包含了一個具備 n 個元素的集合中所有可能的排列（permutation），叫做超排列（superpermutation）。
1993 年，丹尼爾·艾什洛克（Daniel Ashlock）和詹內(nèi)特·蒂洛森（Jenett Tillotson）發(fā)現(xiàn)，如果觀察n取不同值的超排列，我們很快會發(fā)現(xiàn)其中的規(guī)律和階乘（factorial）有關(guān)。階乘寫作 n!，指所有小于或等于 n 的正整數(shù)的乘積（例如 4! = 4 × 3 × 2 × 1）。
如果某個劇集只有 1 集，那么最短的超排列的長度就是 1!。對于包含 2 集的劇集，最短的超排列（121）的長度是 2! + 1!。在 3 集的情況下（例如前面的案例），最短的長度為 3! + 2! + 1!；而到了 4 集的時候，最短的序列是123412314231243121342132413214321，序列長度是 4! + 3! + 2! + 1!。超排列的階乘規(guī)律變成了一種經(jīng)驗智慧（盡管沒人能證明它適用于所有的 n），并且數(shù)學(xué)家后來對 n=5 的情形進行了驗證。
要體現(xiàn) 5 個元素所有可能的排列，序列的最小長度是 5! + 4! + 3! + 2! + 1! = 153。| 圖片來源：Pixabay
直到 2014 年，休斯頓證明這條規(guī)律在 n=6 時不成立，讓數(shù)學(xué)家嚇了一跳。按照階乘計算，以每一種可能的順序觀看6部劇集，播放列表至少包含 873 集，然而休斯頓找到了一種辦法，讓它變成了 872 集。而且，由于有一種簡單的方式能夠?qū)?n 個元素的較短超排列轉(zhuǎn)換成 n+1 個元素的較短超排列，休斯頓的案例說明，階乘規(guī)律對所有 n>6 的情況都不再適用。
休斯頓的工作將超排列問題進行了重構(gòu)，將其轉(zhuǎn)換成著名的旅行推銷員問題（traveling salesman problem），即尋找穿過一系列城市的最短路線。具體而言，超排列與“不對稱”旅行推銷員問題有關(guān)，即連接兩個城市的路線需要收費（不同方向收費可能不同），此時推銷員的目標(biāo)是找到穿過所有城市的最便宜的路線。
這個轉(zhuǎn)換過程很簡單。假設(shè)每種排列都是一座“城市”，再想象連接兩種排列的路線。在超排列問題中，我們希望能夠得到能夠包含所有可能排列的最短的序列，所以我們的目標(biāo)是在各個排列之間“旅行”，每次旅行都會對開始的排列加上幾個字節(jié)。因此，定義每條路線的“路費”為需要在上一個排列后面添加的字節(jié)數(shù)，例如在 n=3 的情況下，從 231 到 312 花費 1 美元，因為我們只要在 231 后面加上一個 2，就能得到 312。按照這樣的設(shè)定，連接城市之間開支最少的路線就對應(yīng)了最短的超排列。
圖片來源：Lucy Reading-Ikkanda/Quanta Magazine / 翻譯：科研圈
這種轉(zhuǎn)換意味著休斯頓可以將解答旅行推銷員問題的算法拿來解決超排列問題。旅行推銷員問題是一個著名的 NP 困難問題，也就是說沒有一種有效的算法能夠適用于所有的情況。但是，有的算法可以高效地解決一部分情況下的問題，而另一些算法能夠計算出足夠接近的答案。休斯頓采用了后者，計算出了那個長度為 872 的超排列。
由于他算出的只是一個近似解，這也許并非最好的超排列。潘通說，數(shù)學(xué)家們正在運行一次大型計算機搜索，尋找 6 個元素的最短超排列。他說：“我們知道這次搜索將在有限的時間內(nèi)完成，但是我們不知道那會是一星期還是一百萬年。沒有進度條。”
錯誤的次序
當(dāng)休斯頓完成那項工作的時候，那篇匿名發(fā)布的 4chan 帖子已經(jīng)在互聯(lián)網(wǎng)的角落里安靜地待了近三年。其實在帖子發(fā)布幾天后，蒙特埃里森大學(xué)（Mount Allison University）的一名數(shù)學(xué)家納撒尼爾·約翰斯頓（Nathaniel Johnston）就在另一個網(wǎng)站上看到了它的副本——他并不是沉迷動漫，只是在谷歌上搜索超排列相關(guān)的內(nèi)容。
約翰斯頓讀了那條證明，覺得它看起來還靠譜，但他并沒有投入太多的精力去自習(xí)檢查。當(dāng)時數(shù)學(xué)家認為對超排列的階乘計算很可能是對的，而當(dāng)你自認為知道了一個問題的準(zhǔn)確答案，那么它的下界看起來就沒什么意思了。換言之，超排列的研究進程也沒有遵守它的播放次序。
約翰斯頓后來在一兩個網(wǎng)站上看到了這個下界，他說：“我不認為有誰留意到這個證明。”
然后，到了今年的 9 月 26 日，加利福尼亞大學(xué)河濱分校（University of California, Riverside）的數(shù)學(xué)家約翰·巴耶茲（John Baez）在推特上發(fā)布了休斯頓 2014 年的發(fā)現(xiàn)，用來舉例介紹本以為顯而易見、實際上并不正確的數(shù)學(xué)規(guī)律。這條推特引起了科幻作家伊根的注意。伊根在幾十年前就讀于數(shù)學(xué)系，后來他成了一名屢屢獲獎的科幻小說家（有趣的是，他在 1994 年的突破性作品就叫《置換城市》（Permutation City）。）伊根在郵件中寫道：“我對數(shù)學(xué)的興趣從未減退。”
伊根想知道能否構(gòu)建一個比休斯頓的答案更短的超排列。他閱讀了相關(guān)文獻，了解如何通過超排列網(wǎng)絡(luò)構(gòu)建較短路線，在幾個星期后就找到了他需要的東西。在一兩天內(nèi)，他算出了 n 個元素的最短超排列的長度上界，就是 n! + (n – 1)! + (n – 2)! + (n – 3)! + n – 3。它和原先的階乘公式相似，但去掉了很多項。
休斯頓說：“這絕對打敗了先前的上界。”
與此同時，4chan 的匿名帖子計算的下界和新的上界極其接近，就是 n! + (n – 1)! + (n – 2)! + n – 3。當(dāng)伊根的答案被公之于眾之后，約翰斯頓提醒其他的數(shù)學(xué)家關(guān)注匿名帖子中的證明，而休斯頓和潘通很快驗證它是正確的。和休斯頓的工作一樣，新的下界和上界都通過旅行推銷員問題實現(xiàn)了超排列：下界體現(xiàn)了必須經(jīng)過的路費大于 1 美元的路線的最小數(shù)量，而上界計算出僅從路費為 1 美元和 2 美元的路線經(jīng)過的方式，適用于不同的 n 值。
研究人員目前正在努力將上界和下界相結(jié)合，找出超排列問題的唯一解。巴耶茲預(yù)言：“也許人們終于要對這個問題蓋棺定論了。現(xiàn)在的形勢不錯。”
而對于涼宮春日的粉絲來說，伊根的計算給出了在僅僅 93,924,230,411 集中看完第一季所有可能順序的實用方式。粉絲們可以馬上開始努力觀看，或者再等等看數(shù)學(xué)家能不能把這個數(shù)字縮小一點。不過匿名網(wǎng)友計算的下界說明，最終波動范圍不太可能超過 4 千萬集。
撰文丨Erica Klarreich
編譯丨戚譯引
文章來源：科研圈（ID：keyanquan）
IEEE Spectrum
《科技縱覽》
官方微信公眾平臺
往期推薦