清华大学自主招生数学题，只考思维，小学生也能做（19年7月10日）

家长是孩子最好的老师，

这是奥数君第905天给出奥数题讲解。

今天的题目是综合应用题，

来自清华大学2009年自主招生考试，

解题所用知识不超过小学3年级。

题目（5星难度）：

一场跑马比赛最多只能有8匹马参赛，假设同一匹马参加每一场比赛的表现都是一样的。问：可否由不多于50场比赛，完全将64匹马的实力排序？

注：比赛只能分出先后，无法记时。

辅导方法：

将题目写给小朋友，

让他自行思考解答，

若20分钟仍然没有思路，

再由家长进行提示性讲解。

讲解思路：

这道题属于综合应用题，

考察的并不是数学知识，

而是算法设计。

乍看上去毫无头绪，

故考虑从简单推广到复杂。

由于64=8*8，

因此从8的倍数开始考虑。

总的解题思路是：

先考虑16匹马的情况，

再考虑32匹马的情况，

最后考虑64匹的情况。

步骤1：

先思考第一个问题，

如果只有16匹马，

通过多少次比赛可以全部排序？

由于每一场比赛只能8匹马参加，

故把16匹马分为2组每组8匹，

第一轮比赛让每组各比赛一场，

通过2场比赛得到了每个组的排序；

第二轮让两个组的前4名一起比赛，

由于16匹马中的前4一定在每组中是前4，

故这次比赛可以得到16匹马中的前4名；

第三轮在两个组中都去掉第二轮的前4名，

然后在每组剩余的马中挑选前4名，

让这8匹马比赛一次，

这就得到了16匹马中的5到8名；

第四轮就让剩下的8匹马比赛一次，

得到了16匹马中的9到16名。

因此通过5场比赛得到了整体排序。

注：但考虑到最不利的情况，

第四轮比赛是必须进行的。

步骤2：

再思考第二个问题，

如果只有32匹马，

通过多少次比赛可以全部排序？

仿照步骤1中的过程，

把32匹马分为2组每组16匹，

第一轮比赛让每组的16匹都排序，

排序的比赛方式按步骤1的方式进行，

共需要2*5=10场比赛；

第二轮让两个组的前4名一起比赛，

由于32匹马中的前4一定在每组中是前4，

故这次比赛可以得到32匹马中的前4名；

第三轮在两个组中都去掉第二轮的前4名，

然后在每组剩余的马中挑选前4名，

让这8匹马比赛一次，

这就得到了32匹马中的5到8名；

……以此类推……

由于每一轮都得到了4匹马的排名，

最后一轮可以得到8匹马的排名，

而32=4*6+8，

故第八轮比赛后可得到全部32匹的排名，

比赛的场次为10+7=17

因此通过17场比赛得到了整体排序。

步骤3：

综合上述几个问题，

考虑原题目的答案。

对于原题中64匹马的情况，

可仿照步骤1和步骤2进行，

把64匹马分为2组每组32匹，

第一轮比赛让每组的32匹都排序，

排序的比赛方式按步骤2的方式进行，

共需要2*17=34场比赛；

从第二轮比赛开始，类似于步骤2，

每一轮比赛得到4匹马的排序，

最后一轮比赛得到8匹马的排序，

由于64=4*14+8，

故第16轮比赛后可得到全部排名。

此时比赛场次为34+15=49，

所以原题的答案是可以。

注：这种排序的方式不一定最优，

排序的方法也并不唯一，

本文只是给出一种满足题意的方法，

欢迎在下方留言给出您的解法。

思考题（3星难度）：

小明说他找到了4个奇数a,b,c,d，使

1/a+1/b+1/c+1/d=1/2019。请问小明说的正确吗？

微信回复“20190710”可获得思考题答案。

注：过4个月之后，关键词回复可能失效。

同类题目链接：