Author: Zilin

上个月在新加坡的时候，正值国际生物奥林匹克竞赛在新加坡国立大学举行。于是不免想去看看 2012 年 IMO 竞赛的题目和各国比赛的结果。 理论上，国际数学奥林匹克竞赛是从来不进行国家排名的。但是，私底下……你懂的。 这次团体的第一名是韩国队思密达，个人总分第一名是新加坡的一位选手 Jeck Lim。这货四次代表新加坡国家队出战，金银铜满分四种情况都集齐了。中国队总分位列第二，中国队在个人排名最高的是 Yiyang She，位列第四。 言归正传，说说今年的题目。今年难度系数也是最有意思的题目当属第三题——欺诈猜数游戏。 广告插播：《欺诈者游戏》今年的剧场版换女主角了，我再也不相信爱情了。 下面是 2012 年 IMO 第三题： “欺诈猜数游戏”在两个玩家甲和乙之间进行， 游戏依赖于两个甲和乙都知道的正整数和。 游戏开始时甲先选定两个整数和，。甲如实告诉乙的值，但对守口如瓶。乙现在试图通过如下方式的提问来获得关于的信息：每次提问，乙任选一个由若干正整数组成的集合（可以重复使用之前提问中使用过的集合），问甲“是否属于？”。乙可以提任意数量的问题。在乙每次提问之后，甲必须对乙的提问立刻回答“是”或“否”，甲可以说谎话，并且说谎的次数没有限制，唯一的限制是甲在任意连续次回答中至少有一次回答是真话。 在乙问完所有想问的问题之后，乙必须指出一个至多包含n个正整数的集合，若属于，则乙获胜；否则甲获胜。证明： 若，则乙可保证获胜； 对所有充分大的整数，存在整数，使得乙无法保证获胜。 扯点题外话，虽然很多年没有做题了。但是此次再次拿起竞赛题思考的时候，发现心智已经成熟了不少，知道如何去细致地处理问题了。 回想高中的那段时间，无论是看竞赛书，还是出去上课，对于做不出的问题，大都是看了书上或是老师的解答之后，感叹解答之妙，但始终对解题动机这一说没有一个理解。 高中竞赛的训练使得我成为了一个熟练的工人，对于一般的问题，只需要将一般的工具试一遍就好了，而遇到非主流问题就一筹莫展了。所以如何提高对我来说一直是一个问题，现在看来，正是缺乏组合问题的训练，以及对待具体问题具体处理的能力。 但是，一旦脱离了那样的环境，反而能静下心去想问题，也能理解为什么说数学是人类心智的荣耀了。 那下面我要开始分析这个谜题了哦，如果想自己做题目的，就别继续看了哦。隆重推荐这道题目的另外一个原因是，做这个谜题的时候纯粹只需要在脑子里面想就可以了，还可以找个人一起玩这个游戏找找感觉。 第一步，将问题转化为等价的容易思考的形式，也就是说，需要回答这个问题：个回答中至少有一次回答是真话究竟意味着什么？ 每次乙提出一个问题“是否属于？”，如果甲回答“是”，那么我们说是可能属于的集合，反之，我们说的补集是可能属于的集合。为了简化，我们称这个集合为可能集。 那么，经过若干轮问答之后，我们得到一连串的可能集。连续个回答中至少有一次回答是真话就意味着：在这一连串的可能集中，任意连续的个可能集中必然有一个可能集真真切切地含了这个元素。也就是说包含于任意个连续可能集的并集。 第二步，从甲和乙的角度分别考虑取胜的策略。针对第一个小问，我们从乙的角度出发考虑问题。 作为乙的智囊团，我们需要向甲提出一系列为难的问题，使得将可能出现的范围不断缩小。不妨我们把注意力先集中在开始的个问题，我们的目标是使得对应的个可能集的并集最小。 不过多久，就能想到一种二分法的策略。 一开始，的出现范围是到中的所有数。那我们的第一个问题就是取出这个集合中一半数量的数问甲，是不是在这个集合中呢？无论甲如何回答，在第一轮问答过后，得到的可能集，记为，其大小最多就是。此处为了分析方便，我们暂时忽略各种取整的细节。 那如何设计第二轮的问题，才能使得两轮问答过后得到的可能集的并尽量小呢？ 啊哈！只需要将在以外的元素分出来一半作为第二次提问的集合就好了，这样无论甲此次如何选择可能集，记为，这两个集合并集的大小最多是。 这样，如此下去，每次我们都取出前面产生可能集以外元素的一半来质问甲就好了。经过论后，可能集并集的大小最多就是，于是通过之前的分析我们一定可以排除这个并集以外的元素了，也就是个元素了。 如果补回之前忽略的取整细节，你立即会发现，只要，那经过这样轮之后，一定能够排除至少一个数字，从而缩小的出现范围。 我们只要反复应用这个战术，每轮过后，只要的出现范围的大小大于等于，我们就能继续排除。 换句话说，我们总是能将的出现范围的大小缩小到以下。 但第一问的实质是让我们将这个范围的大小缩小到，所以我们的方法需要改进，但毫无疑问我们已经开了一个好头。 观察到在这样的策略下，甲的第一次回答应该尽量选择一个较大的可能集，如果甲选择了只有一个元素的可能集，那可大事不妙了。 那能否迫使甲选择只有一个元素的可能集呢？答案是简单的。 只需要一直问甲，是不是就可以了。如果甲连续轮都回答“不是”，那我们就成功排除了这个数。如果甲某次回答“是”，那接下来的个问题，我们如法炮制之前的二分法就可以成功排除个数。 综上所述，只要大于，那我们就能不断地排除一些数。于是当，乙有必胜策略！ 第二个子问题，请听下回分解。