Re: [闲聊] 凉宫春日14集要看多少次才能得到正确排序

楼主: nahsnib (æ‚Ÿ)   2018-10-25 23:24:19
关于这问题刚好是小弟大学时候的图论作业,所以出来献丑解释一下
首先,简化问题,如果动画只有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万年 又有四千多万年的时间看其他番了 可喜可贺
作者: medama ( )   2018-10-25 23:28:00
温馨
作者: kaj1983   2018-10-26 01:06:00
不要让我回想起以前的离散数学啊干!我又睡不着了

Links booklink

Contact Us: admin [ a t ] ucptt.com