在4chan讨论如何播放凉宫,匿名网民为组合数学难题带来进展

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


网友评论:
果然能融入数学问题的名词还是麦乐鸡就够了……
就“观看”来说,有些上下篇的集数不好反转过来吧
当然一来就放送someday in the rain可能和一来就放叹息要好
记得当年看《凉宫春日的忧郁》,不知看到第几集,然后剧情就诡异地无限重复,仿佛度过了无尽的夏天。

发自我的iPhone via Saralin 2.1.1
来自: iPhone客户端
看了三遍才看懂
论文署名会有4chan吗
那年暑假贴吧都在骂京阿尼

  -
4chan宅宅真是人才辈出。。。
4chan网友藏龙卧虎
想折腾自己那么麻烦干嘛,直接看八月
在ok手势,ok to be white ,以及这件事后,4chan给我的印象就是扭曲死宅在粪坑里较真,炸着了外边的人,外边的人不由自主说了句“真香”
宅男沉迷黄暴恐动漫,竟为世界数学难题带来进展
那么假如有某篇论文需要使用这个证明引用该怎么写
“本证明来自4ch”
身败名裂啊


不止有名字,直接一作了
…真特么的魔幻。

标签:    发布日期:06-30