64匹马,在8赛道的赛场上赛跑,即一场可赛八匹马.每匹马每次跑得一样快.问要给64匹马按快慢排序,最不利的情况下,几场比赛一定可以赛完?

Question

64匹马,在8赛道的赛场上赛跑,即一场可赛八匹马.每匹马每次跑得一样快.问要给64匹马按快慢排序,最不利的情况下,几场比赛一定可以赛完?

Answer 1

至今做到：37场.37场：先随意将马排成8*8阵型：01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 1、每一行赛一场,共八场.由对称性,不妨设每一行都是从左到右速度依次减慢.即01,09,17,25,33,41,49,57是八场的冠军.2、下面说明,之后每4场总可以决出8个名次.（1）各组冠军赛一场,（2）各组垫底赛一场,共两场,决出了第一名、第六十四名.且不妨设第一列各马速度由上至下依次变慢.即01是总冠军.（3）现在,总第二名有两匹马候选,02,09.让02,09,10,17四匹马参与第三场.第三场另四匹呢?它们是有类似情况的最慢的几匹马.例如如果64是最慢的,第八列由快到慢依次是08,16,24,32,40,48,56,64,那么,让56,63,55,48四匹马参与第三场.由第三场的结果,总可以知道总第二、第六十三名.下面说明,不管02,09,10,17赛得的结果如何,总第三、四名的候选马不会超过四匹.若02获胜,那么总第三、四名的候选马只有03,04,09,以及10和17两匹中较快的一匹（这两匹已经赛过） 若09获胜,那么第三名实际上已经知道了,是02、10或17中较快的一匹.若是02,则第四名候选马是03,10,17.若是10,则第四名候选马是02,11,17.若是17,则第四名候选马是02,10,18,25.于是,总第三、四名的候选马不会超过四匹.同理,总第六十二、六十一名的候选马也不会超过四匹.（4）将上述总第三、四名的候选马、总第六十二、六十一名的候选马至多不超过八匹,赛一场,于是至此已经决出了前四名后四名共八个名次.不断重复上述过程,直至7个4场后决出了56个名次.3、最后还剩8个名次,用一场解决.总计：8+4*7+1=37场.