[其他] 4chan涼宮春日討論串促進組合數學的進步

https://www.thenewslens.com/article/106880 在4Chan討論如何播放《涼宮春日》動畫，匿名網民為組合數學難題帶來進展 https://warosu.org/sci/thread/S3751105#p3751197 我們想讓你知道的是 在貼圖版討論區4Chan上，一位匿名網民在7年前為「最小超排列」這個數學問題帶來突破 ，現在其貢獻終於被其他數學家發現。 改編自日本作家谷川流輕小說作品的動畫《涼宮春日的憂鬱》2006年版總共有14集，首次 播出時電視台播放順序並未循從故事發展時序。到了2009年，動畫再次播放，但按故事發 生時序播出，並在中途加入新作品。由於2006年版本的播放順序跟故事發生的時序有別， 網絡上有不少關於應以甚麼順序看這套動畫的討論。 2011年，有人在貼圖討論版網站4Chan的科學及數學版（/sci/）上提出「涼宮春日問題」 ︰如果要把《涼宮春日的憂鬱》（2006年版，下同）所有可能的播放次序都看一遍，最少 要看多集？ 排序問題 一般來說，如果動畫有n集的話，可能的排序就會有 1 × 2 × 3 ×… × n 個，這數字 稱為n的階乘（factorial），記作「n!」。隨着n越來越大，n!會急劇增長，14集的動畫 總共有14!個可能次序，即有87,178,291,200——即近872億——種可能。 14集實在太多，讓我們先從簡單的例子開始。假設動畫只有兩集，播放排序僅得兩個可能 ，我們可以先順次序看，然後再倒轉看——以數字代表集數的話如下︰1, 2, 2, 1。如果 我們只在意排序，就不必重複看第二集兩次，以「1, 2, 1」的方式看三集便能達成目標 。 假設動畫有三集，則有6個可能的播放次序︰ 1, 2, 3 1, 3, 2 2, 1, 3 2, 3, 1 3, 1, 2 3, 2, 1 如果以「1, 2, 3, 1, 2, 1, 3, 2, 1」的次序觀看，便可以把上述6個可能排序都看了一 遍。 數學上每一個可能的次序稱為「排列」（permutation），直觀地理解，就是把n件東西不 重複又沒有遺漏地排隊（為方便起見，我們可以把這n件東西以數字代表）。 至於上述的「涼宮春日問題」則討論另一個相關概念，稱為「超排列」（ superpermutation）。對於任何數字n，「n-超排列」就是一個數列，當中包含了n件東西 的所有排列。這樣說好像很抽象，不過我們其實已在上文見過︰「1, 2, 1」就是一個「 2-超排列」；「1, 2, 3, 1, 2, 1, 3, 2, 1」就是一個「3-超排列」。 最小超排列問題 換言之，只要跟着一個「14-超排列」去播放《涼宮春日的憂鬱》，你就能夠以所有可能 的次序去看完這套動畫——前提是你有足夠時間。而「涼宮春日問題」的重點在於以「最 少的集數」去看完，用數學家的語言來說，就是要找到一個「最小超排列」（minimal superpermutation）。 早在1993年，已有數學家提出尋找最小超排列的問題。對於較小的數字，數學家已經找到 其最小超排列。假如總共有5集動畫，按以下次序播放153集便能夠看完所有可能排序︰ 1, 2, 3, 4, 5, 1, 2, 3, 4, 1, 5, 2, 3, 4, 1, 2, 5, 3, 4, 1, 2, 3, 5, 4, 1, 2, 3, 1, 4, 5, 2, 3, 1, 4, 2, 5, 3, 1, 4, 2, 3, 5, 1, 4, 2, 3, 1, 5, 4, 2, 3, 1, 2, 4, 5, 3, 1, 2, 4, 3, 5, 1, 2, 4, 3, 1, 5, 2, 4, 3, 1, 2, 5, 4, 3, 1, 2, 1, 3, 4, 5, 2, 1, 3, 4, 2, 5, 1, 3, 4, 2, 1, 5, 3, 4, 2, 1, 3, 5, 4, 2, 1, 3, 2, 4, 5, 1, 3, 2, 4, 1, 5, 3, 2, 4, 1, 3, 5, 2, 4, 1, 3, 2, 5, 4, 1, 3, 2, 1, 4, 5, 3, 2, 1, 4, 3, 5, 2, 1, 4, 3, 2, 5, 1, 4, 3, 2, 1, 5, 4, 3, 2, 1 要到2014年，才有人證明不存在長度小於153的「5-超排列」。過往有數學家猜想，最小 的「n-超排列」長度為 1! + 2! + 3! + ... + n!。當n等於5或以下時，這個猜想成立， 不過數學家候斯頓（Robin Houston）在2014年找到了一個長度為872的「6-超排列」，比 起猜想的長度873短。即使如此，他也不確定自己找到的是最小超排列。 在上個星期五，科幻小說家伊根（Greg Egan）在Twitter表示他根據數學家威廉斯（ Aaron Williams）一篇論文預印本，修改其方法後找到一個產生超排列的演算法。伊根指 他的演算法所產生的最小「n-超排列」長度為 n! + (n-1)! + (n-2)! + (n-3)! + (n-3) ，當n大於6的時候，長度就會小於猜想的數字，他更寫了一個程式，得出7-／8-／9-超排 列。 利用伊根的公式計算——假設他的方法正確——如果要看完14集涼宮春日動畫的各種順序 ，「只需要」看93,924,230,411集就行。伊根的演算法為最小超排列找到長度上限，那麼 下限是多少呢？ 來自4Chan的證明 上星期二侯斯頓發現，在一個討論「涼宮春日問題」的網站上，有條公式計算最小超排列 的長度下限，而這條公式是已知的最佳結果。網站的內容正好來自2011年4Chan上的討論 。 根據備份網站的記錄，一位化名「Lower bounds」（下限）的網民在「涼宮春日問題」的 討論串中表示︰「我想我證明了下限是 n! + (n-1)! + (n-2)! + (n-3)」，用五則帖文 的篇幅提供證明，並請其他網民檢查有沒有漏洞。 候斯頓跟伊根討論後，認為這位「Lower bounds」的證明應該成立，然而他指出，因為這 個證明不屬於學術文獻的一部分，其他數學家或會猶豫要不要相信及引用，所以這個證明 現在處於一個奇怪的狀態。數學家彭通（Jay Pantone）則把證明以數學論文的形式重寫 ，以便其他數學家閱讀。 雖然證明者身分未明，但匿名並不影響證明是否成立。彭通說︰「數學美麗之處，在於證 明從假設出發，得出結論，你必須說服懷疑的讀者你的證明正確，而這不需要他們得悉你 的身分。」 伊頓以及這位4Chan網民的貢獻，讓我們知道「涼宮春日問題」的答案介乎 93,884,313,611及93,924,230,411之間——即大約播放939億集，便能看完《涼宮春日的 憂鬱》的所有可能排序。候斯頓、彭通及其他數學家現正努力結合兩人的證明，希望得出 能夠準確計算出最小超排列長度的公式。 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.253.168.221 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Math/M.1725105805.A.023.html