最近，有小相知问了我一个小学二年纪的数学题，让我百思不解。大家望望，你能不行做出来：

９辆赛车的速率各不疏导，它们要比快慢，但莫得计时器具，只可在赛道上比谁先谁后，而且每次最多只可有３辆车比赛。那么，最少比几次，能保证选出最快的２辆赛车？

我做了好半天也没想出谜底，于是我就接头了我的学生507（此人毕业于北京大学数学系，当年也屡次帮我解答数知识题，甚是历害），她只花了３秒钟就告诉了我谜底：５次。

5次是可行的

５０７的圭臬是这么的：

最先每三辆车一组，分红三组比小组赛。每个小组都能排出章程。

然后，让三个小组的第又名进行一场决赛，就能选出信得过的第又名。

这时，决赛中的第二名和总冠军在小组赛时的第二名，都是只输给了总冠军，它们俩谁快呢？还要比一下。谁赢了谁等于信得过的第二名。是以，咱们还需要一场附加赛。

算起来，３场小组赛，１场总决赛，１场附加赛。一共等于５场比赛啦！

4次为什么不行

那时，我在相知圈里发了这个问题乐动体育App下载，许多同学都很快给出了５次的谜底。不外乐动体育App下载，有两名海外金牌，一直在商量为什么５次等于最少的，为什么４次就不行？

自后，507又告诉了一种圭臬，实在不错解释４次是不行的。她选定的是图论＋反证法的圭臬。

最先，咱们把问题意会为：需要从９辆车中，区别出冠军和亚军，咱们觉得这么意会题意是合理的，而且责罚起来比拟约略。若是你不区别冠军和亚军，问题可能会稍稍复杂一些。

然后，把每一辆车看作一个点，用每一场比赛的遵循进行连线，这么就组成了一个图。具体来说：比赛的经由等于给三辆车排序，若是咱们把相邻获利的两辆车用有向线段聚合起来，一场比赛就会出现两条线。比如，在一次比赛中，汽车１最快，汽车２其次，汽车３最慢，那么它们之间的图应该是这么的：

若是举行４场比赛，最多大约画出８条线。为了找到冠军和亚军，这８条线必须把９个点连起来，造成一个单一的、树状的、莫得闭环的图，比如底下这个样貌：

不错判断出冠军和亚军

大家不错想想：若是图不是单一的，而是分红两支，那么就没主义判断谁才是信得过的第一。

有两辆赛车可能是冠军，亚军也无法判断

若是图不是树状，而是中间存在闭环，那么就糜掷了一条线，８条线毫不可能把９个点聚合起来。

造成一个闭环，至少需要９根线智力把９个点聚合起来

底下咱们要论证：用８根线，不可能保证把９个点连成咱们要求的图。

最先：为了找到冠军，冠车和亚军车一定同场竞技过。因为，它们比其它车都快，若是它们莫得比赛过，都会保持不败战绩，就无法区别出谁是冠军了。它们比赛时，冠军一定第一，亚军一定第二，是以冠军和亚军之间有连线。

然后，为了找到亚军，亚军和季军一定同场竞技过。因为，除了冠军除外，这两辆车比其它车都要快。若是它们莫得比赛过，就无法区别出谁是亚军。相通的酷爱酷爱酷爱酷爱，亚军和季军之间有连线。

冠军、亚军、季军之间一定有连线

凭证刚才所说，图中不行造成闭环，既然冠军和亚军之间、亚军和季军之间一定有连线，那么冠军和季军之间是不不错有连线的。关联词你要戒备：在咱们进行第一场比赛时，马上选拔了三辆车，若是选拔的三辆车分别是冠军、季军和第四名，那么比赛后，凭证咱们的构造规定，冠军和季军分列小组第一和第二，它们之间会做出一条连线。这么，通盘比赛戒指后，冠军、亚军、季军就会出现一个闭环。

大家戒备：冠军和季军之间的这条线不是一定存在，闭环也不一定存在。但是由于率先咱们衰退信息，马上选拔车辆比赛，咱们不行保证冠军、季军和第四名不会碰在沿途，咱们也无法保证幸免闭环的出现。而一朝出现闭环，就不可能用８条线把９个点连成一个单一的树状图，也就不行判断出冠军和亚军了。

通盘的逻辑经由是这么的：

总而言之，８条线不行保证把９个点连成答允要求的图，是以４场比赛也不行保证从９辆车中找到冠军和亚军，５次比赛是最少情况。

你看，一个小学二年纪问题，真实连图论和反证法都用上了。

还能再过劲少量吗？

咱们能让这个问题变得愈增加半一些吗？

比如：若是有ｎ²辆车，每次比赛只消ｎ辆车参赛，在莫得计时器具的情况下，至少比赛些许次，智力保证找到第又名和第二名？

这个问题很约略，圭臬亦然肖似的，你不错思考一下再往下看。

最先进行小组赛：每场比赛ｎ辆车，共有ｎ场比赛。按照刚才的构造圭臬，咱们能把每一小组的赛车排序，而且进行连线。

ｎ场小组赛后，每一小组的章程都排好了

然后，咱们再让每场小组赛的第又名进行一场总决赛，找到冠军。

１场决赛后，冠军找到了

终末，冠军小组赛时的第二名和总决赛的第二名，再进行一场附加赛，找到亚军就好了。比如底下这种情况：

１场附加赛后，找到亚军

最终，咱们通过ｎ场小组赛、１场总决赛、１场附加赛，找到了冠军和亚军，一共需要ｎ+2场比赛。

你能解释ｎ+2是最少的情况吗？

圭臬和刚才一样:

若是只需要ｎ+1场比赛，每一场比赛只可对ｎ辆车排序，能连ｎ－１条线，是以通盘比赛一共大约连(n+1)(n-1)＝ｎ²-1条线。

用ｎ²-1条线，聚合ｎ²个点，找到冠亚军，必须画出一个单一、树状、无闭环的图。

关联词，凭证９辆车时相通的酷爱酷爱酷爱酷爱，冠军、亚军、季军之间有可能出现闭环。

是以，用ｎ+1场比赛，无法保证找到冠亚军。ｎ+2是问题的解。

这个小学二年纪数学题，可能好多同学都能猜度谜底。仅仅要解释它，实在不是一件容易的事。而且，到现在为止，咱们还莫得找到这个问题的一般谜底，若是你称心的话，不错行远自迩的思考以下问题。事前声明，除了第一个问题我找到了谜底，背面两个还莫得思考出来。

问题１：若是有ｎⁿ辆车，每次比赛最多有ｎ辆车，那么最少比赛些许次，智力保证找到冠军和亚军？

问题２：若是有ｎ辆车，每次比赛最多ｍ辆车（ｍ＜ｎ），那么至少比赛些许次，智力保证找到冠军和亚军？

问题３：若是有ｎ辆车，每次比赛最多ｍ辆车（ｍ＜ｎ），要笃定前ｋ辆车的名次（ｋ＜ｎ），至少要比赛些许场？

若是你都想出来了，你至少达到了小学三年纪水平。

END