25匹马中找出跑的最快的三匹马

问题描述:

Given 25 horses, find the best 3 horses with minimum number of races. Each race can have only 5 horses. You don't have a timer.

答案: 七次

详细解答:

首先每五匹马比赛一次,这样我们得到五组组内的排序,花费了五次比赛。

然后,五组中的小组冠军组成冠军联赛,冠军联赛的冠军就是年度总冠军啦,也就是我们需要找到的最能跑的马。

可是,接下来怎么只比赛一次就找到年度亚军和年度季军呢。

我们来辨别一下哪些马有可能获得这两个殊荣。首先年度总冠军所在的小组的第二名和第三名是有希望的,然后,冠军联赛中的亚军以及其所在小组的亚军也是有可能的,再然后,冠军联赛的季军也是有可能的,这样一共是五匹马,哈哈,可以比赛了。这场比赛的冠亚军就是我们的年度亚军和季军啦。

到此,我们诞生了冠亚季三军,完成使命了。可是正确性怎么来保证呢?

正确性证明:

首先,对于冠军,这个毫无疑问,王中王必然是大王。

对于亚季军,我们来说明一下我们选定的参加第七次比赛的那五匹马,其他马都不可能。

为了表述方便,我们按照冠军联赛的比赛结果来给组排序,组内顺序按照小组内部比赛结果来确定

A1 B1 C1 D1 E1
A2 B2 C2    
A3        
A4        
A5        

我们注意到表格中越靠左上角的马相对跑得快。

D,E组中的马没有资格了?原因在于B1,C1肯定比他们都快,所以他们不可能是年度亚军和年度季军。

C2-C5是没有资格的,为什么呢?因为B1,C1肯定比他快。

B3-B5也是不行的,原因在于B1,B2肯定比他们快。

同样的,A4,A5也不行。

那么有资格角逐我们年度亚军季军的也就是A2,A3,B1,B2,C1五匹马了。

到此,正确性证明完毕。

差不多该睡觉了。

原文地址:https://www.cnblogs.com/xubenben/p/3393346.html