64匹马能否通过50场比赛比出任意两匹马之间的优劣(每场比赛至多8匹马参赛)

这是2009年清华大学自主招生数学试题(理综)。


思考时间,答案在下面(字体是白色的)。


这道题其实考的是归并排序。


首先将马分为8组,每组排一下序,就比了8场。


然后再将这8组合并为4组,两两合并。


比如A和B组合并:


选A组的前4名和4个B组的前4名,比一场,如果从A中的选出的第4名比B中选出的第4名排名高,那么在A中的选出的第4名前和他自己一定是这些马中靠前的,于是把他们排到新的队中,其余马回到原来的位置;否则,同理分析。所以这样比一场可以确定至少4匹马在新的小组中的的位置。


接下来在剩下的马中继续这样做,直到所有马在新的小组中的位置都确定了。


由于每次都可以至少确定4匹马的位置,而且最后还剩8匹马时只需要比一次就可以确定8匹马的位置,所以两个8匹马的有序的小组合并为一个16匹马的有序小组只需要(16-8)/4+1=3次比赛。


所以8个8匹马的有序的小组合并为4个16匹马的有序小组需要4*3=12次比赛。


所以4个16匹马的有序的小组合并为2个32匹马的有序小组需要2*7=14次比赛。


所以2个32匹马的有序的小组合并为1个64匹马的有序小组需要1*15=15次比赛。


所以一共只需比49场就可以了。