關於這問題剛好是小弟大學時候的圖論作業,所以出來獻醜解釋一下
首先,簡化問題,如果動畫只有2集,標記為AB,你不曉得順序是AB還是BA,所以只好都
看。
但其實你只要ABA或者BAB這樣,看3集一定可以保證你至少看到一次正確的,所以不用看
4集的時間。
那如果是ABC三集呢?
所有可能的排序有6!種,那麼我們只要ABC ABA CBA,看9集就好,不用看3*3!=18
因為BCA這種排序法,跟前面的ABC共用了BC,所以只要多看1集就好。
因此,我們可以輕易地找出這種算法的下限,14集的情況因為有14!種排序法,
假設都剛好只要多看1集,那我們得看(14-1)+14!集,不過這顯然太理想了。
例如上面的例子中,ABCAB,到了這邊,顯然無法在下一步中找到新的組合,勢必會有浪費
的狀況。
然而這類問題的精確答案,或者說給定任意N,是否能找到公式f(N)就是最短長度,
卻一直都沒有什麼令人驚豔的成就,大多都只是上界與下界的削減,
另外一個特色就是數字會暴增的非常恐怖,光是要處理5集的狀況就可以讓人崩潰。
圖論中相似的問題還有很多,其中最有名的也許是「Happy ending question」,
由一個女數學家所提出,題目是:「平面上不共線任意N點,至少要多少才能保證會有一個
凸M邊形產生?(M>3)」
以M=4做例子,N至少要是5,因為我們可以畫出一個三角形內含一點,這四點只能構成凹四
邊形。然而加入第五點之後,必定會產生出一個凸四邊形。
至於為啥這個問題會被叫做Happy ending question呢,因為有個想追求她數學家,拚命找
出這個問題的一個上界。
雖然這個問題到現在也還是沒有一個精確的解答,不過,既然叫做Happy ending question
我想大家也都知道這兩人是否幸福吧。
※ 引述《marada (直笛朋友)》之銘言:
: 好消息來源:
: https://hk.thenewslens.com/article/106880
: 若要看完14集動畫所有的排序最笨的方法是 14集*14!種 和猴子排序的期望值一樣
: 要看~1.2205兆次.. 一小時三集 ~4560萬年
: 但若允許看的時候可以重疊重複部分 以三集為例:
: 1 2 3 1 2 1 3 2 1 這數列包含了所有 3!種的1~3排序
: 123 231 312 213 132 321 可以省下一半的集數
: .........
: 那14集可以省多少呢? 恩...目前為止沒有準確公式,但是最近有人給出
: 新的上下界分別為 93,924,230,411 > 正確次數 > 93,884,313,611
: 一小時三集 ~357萬年 又有四千多萬年的時間看其他番了 可喜可賀