小学二年级数学题,李永乐居然做不出来
9辆赛车的速度各不相同,它们要比快慢,但没有计时工具,只能在赛道上比谁先谁后,而且每次最多只能有3辆车比赛。那么,最少比几次,能保证选出最快的2辆赛车?
可以判断出冠军和亚军
有两辆赛车可能是冠军,亚军也无法判断
形成一个闭环,至少需要9根线才能把9个点连接起来
首先:为了找到冠军,冠车和亚军车一定同场竞技过。因为,它们比其它车都快,如果它们没有比赛过,都会保持不败战绩,就无法区分出谁是冠军了。它们比赛时,冠军一定第一,亚军一定第二,所以冠军和亚军之间有连线。
然后,为了找到亚军,亚军和季军一定同场竞技过。因为,除了冠军以外,这两辆车比其它车都要快。如果它们没有比赛过,就无法区分出谁是亚军。同样的道理,亚军和季军之间有连线。
冠军、亚军、季军之间一定有连线
根据刚才所说,图中不能形成闭环,既然冠军和亚军之间、亚军和季军之间一定有连线,那么冠军和季军之间是不可以有连线的。可是你要注意:在我们进行第一场比赛时,随机选择了三辆车,如果选择的三辆车分别是冠军、季军和第四名,那么比赛后,根据我们的构造规则,冠军和季军分列小组第一和第二,它们之间会做出一条连线。这样,所有比赛结束后,冠军、亚军、季军就会出现一个闭环。
大家注意:冠军和季军之间的这条线不是一定存在,闭环也不一定存在。但是由于最初我们缺乏信息,随机选择车辆比赛,我们不能保证冠军、季军和第四名不会碰在一起,我们也无法保证避免闭环的出现。而一旦出现闭环,就不可能用8条线把9个点连成一个单一的树状图,也就不能判断出冠军和亚军了。
比如:如果有n²辆车,每次比赛只有n辆车参赛,在没有计时工具的情况下,至少比赛多少次,才能保证找到第一名和第二名?
n场小组赛后,每一小组的顺序都排好了
1场决赛后,冠军找到了
1场附加赛后,找到亚军
你能证明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),至少要比赛多少场?
微信扫码关注该文公众号作者