李永乐老师求助一道小学数学题,他居然做不出来!(3)

2022-07-13 17:52  腾讯

根据刚才所说,图中不能形成闭环,既然冠军和亚军之间、亚军和季军之间一定有连线,那么冠军和季军之间是不可以有连线的。可是你要注意:在我们进行第一场比赛时,随机选择了三辆车,如果选择的三辆车分别是冠军、季军和第四名,那么比赛后,根据我们的构造规则,冠军和季军分列小组第一和第二,它们之间会做出一条连线。这样,所有比赛结束后,冠军、亚军、季军就会出现一个闭环。

大家注意:冠军和季军之间的这条线不是一定存在,闭环也不一定存在。但是由于最初我们缺乏信息,随机选择车辆比赛,我们不能保证冠军、季军和第四名不会碰在一起,我们也无法保证避免闭环的出现。而一旦出现闭环,就不可能用8条线把9个点连成一个单一的树状图,也就不能判断出冠军和亚军了。

整个的逻辑过程是这样的:

综上所述,8条线不能保证把9个点连成满足条件的图,所以4场比赛也不能保证从9辆车中找到冠军和亚军,5次比赛是最少情况。

你看,一个小学二年级问题,居然连图论和反证法都用上了。

还能再给力一点吗?

我们能让这个问题变得更加普遍一些吗?

比如:如果有n²辆车,每次比赛只有n辆车参赛,在没有计时工具的情况下,至少比赛多少次,才能保证找到第一名和第二名?

这个问题很简单,方法也是类似的,你可以思考一下再往下看。

首先进行小组赛:每场比赛n辆车,共有n场比赛。按照刚才的构造方法,我们能把每一小组的赛车排序,并且进行连线。

n场小组赛后,每一小组的顺序都排好了

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

1场决赛后,冠军找到了

最后,冠军小组赛时的第二名和总决赛的第二名,再进行一场附加赛,找到亚军就好了。比如下面这种情况:

1场附加赛后,找到亚军

最终,我们通过n场小组赛、1场总决赛、1场附加赛,找到了冠军和亚军,一共需要n+2场比赛。

你能证明n+2是最少的情况吗?

方法和刚才一样:

如果只需要n+1场比赛,每一场比赛只能对n辆车排序,能连n-1条线,所以所有比赛一共能够连(n+1)(n-1)=n²-1条线。

用n²-1条线,连接n²个点,找到冠亚军,必须画出一个单一、树状、无闭环的图。

可是,根据9辆车时同样的道理,冠军、亚军、季军之间有可能出现闭环。

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

这个小学二年级数学题,可能很多同学都能想到答案。只是要证明它,的确不是一件容易的事。而且,到目前为止,我们还没有找到这个问题的一般答案,如果你愿意的话,可以由浅入深的思考以下问题。事先声明,除了第一个问题我找到了答案,后面两个还没有思考出来。

问题1:如果有nⁿ辆车,每次比赛最多有n辆车,那么最少比赛多少次,才能保证找到冠军和亚军?

问题2:如果有n辆车,每次比赛最多m辆车(m<n),那么至少比赛多少次,才能保证找到冠军和亚军?

问题3:如果有n辆车,每次比赛最多m辆车(m<n),要确定前k辆车的排名(k<n),至少要比赛多少场?

如果你都想出来了,你至少达到了小学三年级水平。