来自前苏联的数学竞赛题，巧妙到让人叹为观止（19年2月25日）

家长是孩子最好的老师，

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

今天的题目是赛制问题，

题目来自前苏联的一次数学竞赛，

所用知识不超过小学5年级。

题目（5星难度）：

某地举办国际象棋比赛，结果报名的人很多。负责比赛的乔娜说：报名比赛的共有100多万人，如果再有1000个人报名，总人数就是32^4了。比赛实行淘汰制，每轮比赛所有人抽签两两配对比赛，输的人立即淘汰，赢的人晋级下一轮淘汰赛，直到决出冠军。但比赛中难免有人轮空，比如9个人参加淘汰赛，一定有1个人轮空，轮空的人自动晋级下一轮淘汰赛，把这种情况称为有1人次轮空。问比赛到最后有多少人次轮空？

注: 32^4表示32的4次方。

讲解思路：

这道题属于赛制问题，

显然若参加淘汰赛人数出现奇数，

则一定有1人次轮空。

如果数字比较小，

我们可以直接计算，

但题目中给定的数字非常大，

不适合正面计算，

为此采用反面思考的办法。

解题过程分以下几步：

先思考没有人轮空的情况，

再思考1000和轮空的人有何关系，

最后计算轮空的人次。

步骤1：                  

先思考第一个问题，

参赛总人数是多少时，

永远不会有人轮空？

由于比赛是两两配对的，

若某次淘汰赛有奇数名选手，

则一定有1人轮空。

反之若每次都是偶数名，

则永远不会有人轮空。

因此若初始总人数是2^n，

则永远不会有人轮空。

步骤2：

再思考第二个问题，

1000和轮空的人有何关系？

如果参赛总人数再多1000，

则总人数是32^4=2^20，

根据步骤1的结论，

永远不会有人轮空。

现在少了1000人，

我们可以给初始人数虚增1000，

把虚增的人看作蓝色人，

采用逆向排除的方法，

让蓝色人也同步参加比赛，

比赛的方案如下：

每轮淘汰赛开始时，

若非蓝色人是偶数名，

则蓝色人两两互相配对比赛，

淘汰一半蓝色人；

若非蓝色人是奇数名，

由于参赛总人数都是偶数名，

故此时蓝色人也是奇数名，

则蓝色人除两两配对比赛外，

剩余的1个蓝色人与本应轮空的那个非蓝色人比赛，

且比赛结果是非蓝色人胜。

此时在这个比赛方案下，

每有1人次轮空，

就有一次蓝色人出现奇数，

轮空的总人次可以按此计算。

步骤3：

综合上述几个问题，

考虑原题目的答案。

在步骤2的比赛方案下，

第1轮淘汰赛，

蓝色人数从1000到了500；

第2轮淘汰赛，

蓝色人数从500到了250；

第3轮淘汰赛，

蓝色人数从250到了125；

第4轮淘汰赛，

蓝色人数从125到了62；

接下来的几轮淘汰赛中，

蓝色人数分别是

31，15，7，3，1，0。

上述过程中，

蓝色人出现了6次奇数，

所以共有6人次轮空。

注:步骤3有一个简便算法，

把1000化为二进制是1111101000，

其中共有6个1，

所以共出现6人次轮空。

这是一个很有趣的小结论

感兴趣的朋友可以自行证明，

欢迎把您的证明方法在下方留言。

思考题（3星难度）：

对原题改个数字。

某地举办国际象棋比赛，结果报名的人很多。负责比赛的乔娜说：报名比赛的共有37名。比赛实行淘汰制，每轮比赛所有人抽签两两配对比赛，输的人立即淘汰，赢的人晋级下一轮淘汰赛，直到决出冠军。但比赛中难免有人轮空，比如9个人参加淘汰赛，一定有1个人轮空，轮空的人自动进入下一轮淘汰赛，把这种情况称为有1人次轮空。问比赛到最后有多少人次轮空？

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

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

同类题目链接：

每天坚持原创不易，

您点击的每一次“好看”和厂告，

都是对我最好的认可，

谢谢您的认可。