问题:
一共有25匹马,有一个赛场,赛场有5个赛道,就是说最多同时可以有5匹马一起比赛。假设每匹马都跑的很稳定,不用任何其他工具,只通过马与马之间的比赛,试问最少得比多少场才能知道跑得最快的5匹马?
思路:
先将25匹马分成五组,进行五场比赛。第六场比赛可以考虑都取各个小组的第一名(或第二名)。假设都取各小组的第一名,根据这场比赛的排名,将原来的小组分别编号为a、b、c、d、e,并将原来的25匹马分别编号为:
a1 b1 c1 d1 e1
a2 b2 c2 d2 e2
a3 b3 c3 d3 e3
a4 b4 c4 d4 e4
a5 b5 c5 d5 e5
其中Xi,X表示组的编号,i为在该组的排名,则有:
a1 > b1 > c1 > d1 > e1
a1 > a2 > a3 > a4 > a5
b1 > b2 > b3 > b4 > b5
.......
e1 > e2 > e3 > e4 > e5
注意到:跑得比a3、b2、c1这三匹马都快的只可能是a1、a2、b1,因而a3、b2、c1三匹马中跑得最快的必然是前四之一。因此,第七场比赛,这三匹马必然参加,剩下两个名额待定。先考虑这三匹马的排名:
(下面用[]集合表示已确定是前五的马,用{}集合表示剩下的马中所有有可能是前五的马。)
① a3 b2 c1 或 a3 c1 b2: 则 [a1, a2, a3] + {a4,a5,b1,b2,c1}
② b2 a3 c1: [a1,b1,b2] + { a2,a3, b3,b4}
③ b2 c1 a3: [a1,b1,b2] + {a2,b3,b4,c1,c2,d1}
④ c1 a3 b2: [a1,b1,c1] + {a2,c2,c3,d1,d2,e1 }
为了能在第八场确定前五,必须将上面的{a2,b3,b4,c1,c2,d1} 和{a2,c2,c3,d1,d2,e1} 的候选马匹数减少到五匹,因而剩下的两个名额必须是这两个集合的重复元素,即是{a2, c2, d1}中的两个。由于a2跑得比a3快,若选择a2的话,不能利用前面的分析,因而剩下两匹马选择 c2 和 d1。
第七场比赛:a3、b2、c1、c2、d1 的前两名是:
① a3 : [a1, a2, a3] + {a4, a5, b1, b2, c1}的前二名(由第八场比赛决定)
② b2 a3: [a1, b1, b2] + {a2,a3, b3,b4}的前二名
③ b2 c1: [a1, b1, b2] + {a2, b3, b4, c1, max(c2, d1)} 的前二名
④ c1 a3: [a1,a2,a3,b1,c1] (第七场就可确定前五)
⑤ c1 b2: [a1,b1,c1] + {a2,b2,b3,c2,d1}的前二名
⑥ c1 c2: [a1,b1,c1,c2] + {a2,b2,c3,d1}的第一名
⑦ c1 d1: [a1,b1,c1,d1] + {a2,b2,c2,d2,e1}的第一名
因而,最少七场比赛,最多八场比赛就可确定跑得最快的5匹马。