找到11场的这个答案（你做的事情）是trivial的。
但是，严格的来说，你还得证明不可能比11场少（i.e.证明11是个lower bound），这个就需要一点不那么trivial的knowledge，虽然还是很简单(但应该还是挺麻烦的)。
这样的话，图论应该是比较简单的解法了。（本质上是单纯count 比较的次数，你可以想象一个比较就是在两个node，也就是两个马，之间建立一个directed edge。你每赛马一次可以建立多少edge呢？你至少需要多少个edge才能找到最快的四个呢？如果你有一个algorithm的话，如果有一个adversary可以安排出来一个最差的scenario会怎么样呢。）
Mark Joshi表示后继有人 
想了一下好像并不简单啊。因为有其他场次的信息，赛马一次可以建立很多edge.
前四的证明比较啰嗦，前二的证明比较简洁：
李永乐把保证选出前两名理解为要能知道谁第一谁第二，同时视频里要证明的是4次不行，而9个点用8条线才能联通，所以得出结论不能有多余的连线。相对而言，这道赛马题似乎复杂得多。
明天猎头喊你去花街报道
lower bound也不难，分情况讨论的流程很类似。考虑马的摆放是adversarial的，最快的马必须被跑一次才能发现，所以每匹马至少跑一次，trivial lower bound是8场。然后考虑到这八场最快的8匹马不一定能包括所有前四名，至少需要第9场。再往上讨论起来就比较复杂了。
FYI，你描述的问题领域是sorting network，和常人说的“图论”(graph）不太一样。
Emmm。我同意到10都不难。（通过counting证明至少要9，反证，证明9也不行）从10到11，我觉得讨论adversary还是有一些复杂度的。
谢谢~我确实不了解sorting network，其实也是顺着前面人的“图论”往下说。不过，因为学过太多和graph相关的东西，我个人对于图论的definition就过于的广了，只要稍微带上（G,V,E）我都觉算和graph theory相关了。
证明lower bound最简单的数学工具应该是用信息论来做
这个没用，worst case一样是11。
真别吹牛，要证明lower bound是11是很困难的。上面几个提了几个方法的可以自己试试看，看看能不能证出来。
这道题找到11轮的方法是小学奥赛，证明lower bound至少是9是初中奥赛，10是高中奥赛。到11可能必须要借助计算机。
是，但是超过50%的概率省掉一轮还是有优化意义的
快排worst case也N方呀
mergesort的worstcase就是nlgn 
离散的信息论我看大部分证明都是在 counting，最基础的情况也不容易
不懂赛马，就不能8场，计时，排序一下吗 
