在4Chan討論如何播放《涼宮春日》動畫,匿名網民為組合數學難題帶來進展

在4Chan討論如何播放《涼宮春日》動畫,匿名網民為組合數學難題帶來進展
Photo Credit: Koji Sasahara / AP Photo / 達志影像
我們想讓你知道的是

在貼圖版討論區4Chan上,一位匿名網民在7年前為「最小超排列」這個數學問題帶來突破,現在其貢獻終於被其他數學家發現。

唸給你聽
powered by Cyberon

改編自日本作家谷川流輕小說作品的動畫《涼宮春日的憂鬱》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億集,便能看完《涼宮春日的憂鬱》的所有可能排序。候斯頓、彭通及其他數學家現正努力結合兩人的證明,希望得出能夠準確計算出最小超排列長度的公式。

相關文章︰

資料來源︰