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