64匹马8条赛道找最快4匹的拆分讨论

:joy: :joy: :joy: 找到11场的这个答案(你做的事情)是trivial的。

但是,严格的来说,你还得证明不可能比11场少(i.e.证明11是个lower bound),这个就需要一点不那么trivial的knowledge,虽然还是很简单(但应该还是挺麻烦的)。

这样的话,图论应该是比较简单的解法了。(本质上是单纯count 比较的次数,你可以想象一个比较就是在两个node,也就是两个马,之间建立一个directed edge。你每赛马一次可以建立多少edge呢?你至少需要多少个edge才能找到最快的四个呢?如果你有一个algorithm的话,如果有一个adversary可以安排出来一个最差的scenario会怎么样呢。)

6 个赞

Mark Joshi表示后继有人 :yaoming:

想了一下好像并不简单啊。因为有其他场次的信息,赛马一次可以建立很多edge.

1 个赞

前四的证明比较啰嗦,前二的证明比较简洁:

  1. counting本身应该不足以。(counting本身可以证明你需要多少组可以找到最大的,然后帮助你把bound至少放到9)
  2. 然后应该用到一些adversary argument(也就是反证法的地方),这样可以让你从9到11.
  3. 这道题有些类似多少comparison才可以找到 largest, second largest, third largest… number.
    4.以及没错,确实谈不上简单。

李永乐把保证选出前两名理解为要能知道谁第一谁第二,同时视频里要证明的是4次不行,而9个点用8条线才能联通,所以得出结论不能有多余的连线。相对而言,这道赛马题似乎复杂得多。

1 个赞

明天猎头喊你去花街报道

lower bound也不难,分情况讨论的流程很类似。考虑马的摆放是adversarial的,最快的马必须被跑一次才能发现,所以每匹马至少跑一次,trivial lower bound是8场。然后考虑到这八场最快的8匹马不一定能包括所有前四名,至少需要第9场。再往上讨论起来就比较复杂了。

FYI,你描述的问题领域是sorting network,和常人说的“图论”(graph)不太一样。

2 个赞

Emmm。我同意到10都不难。(通过counting证明至少要9,反证,证明9也不行)从10到11,我觉得讨论adversary还是有一些复杂度的。

谢谢~我确实不了解sorting network,其实也是顺着前面人的“图论”往下说。不过,因为学过太多和graph相关的东西,我个人对于图论的definition就过于的广了,只要稍微带上(G,V,E)我都觉算和graph theory相关了。

https://zhuanlan.zhihu.com/p/398143738?utm_id=0

这个最清晰了感觉

你这个厉害了啊,最后结论 还有conditional 的

证明lower bound最简单的数学工具应该是用信息论来做

2 个赞

这个没用,worst case一样是11。

真别吹牛,要证明lower bound是11是很困难的。上面几个提了几个方法的可以自己试试看,看看能不能证出来。

这道题找到11轮的方法是小学奥赛,证明lower bound至少是9是初中奥赛,10是高中奥赛。到11可能必须要借助计算机。

2 个赞

是,但是超过50%的概率省掉一轮还是有优化意义的
快排worst case也N方呀

mergesort的worstcase就是nlgn :troll:

离散的信息论我看大部分证明都是在 counting,最基础的情况也不容易

1 个赞

不懂赛马,就不能8场,计时,排序一下吗 :clown_face: