欺诈猜数游戏(上)

上个月在新加坡的时候,正值国际生物奥林匹克竞赛在新加坡国立大学举行。于是不免想去看看 2012 年 IMO 竞赛的题目和各国比赛的结果。

理论上,国际数学奥林匹克竞赛是从来不进行国家排名的。但是,私底下……你懂的。

这次团体的第一名是韩国队思密达,个人总分第一名是新加坡的一位选手 Jeck Lim。这货四次代表新加坡国家队出战,金银铜满分四种情况都集齐了。中国队总分位列第二,中国队在个人排名最高的是 Yiyang She,位列第四。

言归正传,说说今年的题目。今年难度系数也是最有意思的题目当属第三题——欺诈猜数游戏。

广告插播:《欺诈者游戏》今年的剧场版换女主角了,我再也不相信爱情了。

下面是 2012 年 IMO 第三题:

“欺诈猜数游戏”在两个玩家甲和乙之间进行, 游戏依赖于两个甲和乙都知道的正整数kn
游戏开始时甲先选定两个整数xN1\leq x\leq N。甲如实告诉乙N的值,但对x守口如瓶。乙现在试图通过如下方式的提问来获得关于x的信息:每次提问,乙任选一个由若干正整数组成的集合S(可以重复使用之前提问中使用过的集合),问甲“x是否属于S?”。乙可以提任意数量的问题。在乙每次提问之后,甲必须对乙的提问立刻回答“是”或“否”,甲可以说谎话,并且说谎的次数没有限制,唯一的限制是甲在任意连续k+1次回答中至少有一次回答是真话。

在乙问完所有想问的问题之后,乙必须指出一个至多包含n个正整数的集合X,若x属于X,则乙获胜;否则甲获胜。证明:

  1. n\geq 2^k,则乙可保证获胜;
  2. 对所有充分大的整数k,存在整数n\geq 1.99^k,使得乙无法保证获胜。

扯点题外话,虽然很多年没有做题了。但是此次再次拿起竞赛题思考的时候,发现心智已经成熟了不少,知道如何去细致地处理问题了。

回想高中的那段时间,无论是看竞赛书,还是出去上课,对于做不出的问题,大都是看了书上或是老师的解答之后,感叹解答之妙,但始终对解题动机这一说没有一个理解。

高中竞赛的训练使得我成为了一个熟练的工人,对于一般的问题,只需要将一般的工具试一遍就好了,而遇到非主流问题就一筹莫展了。所以如何提高对我来说一直是一个问题,现在看来,正是缺乏组合问题的训练,以及对待具体问题具体处理的能力。

但是,一旦脱离了那样的环境,反而能静下心去想问题,也能理解为什么说数学是人类心智的荣耀了。

那下面我要开始分析这个谜题了哦,如果想自己做题目的,就别继续看了哦。隆重推荐这道题目的另外一个原因是,做这个谜题的时候纯粹只需要在脑子里面想就可以了,还可以找个人一起玩这个游戏找找感觉。

第一步,将问题转化为等价的容易思考的形式,也就是说,需要回答这个问题:k+1个回答中至少有一次回答是真话究竟意味着什么?

每次乙提出一个问题“x是否属于S?”,如果甲回答“是”,那么我们说Sx可能属于的集合,反之,我们说S的补集是x可能属于的集合。为了简化,我们称这个集合为可能集。

那么,经过若干轮问答之后,我们得到一连串的可能集。连续k+1个回答中至少有一次回答是真话就意味着:在这一连串的可能集中,任意连续的k+1个可能集中必然有一个可能集真真切切地含了x这个元素。也就是说x包含于任意k+1个连续可能集的并集。

第二步,从甲和乙的角度分别考虑取胜的策略。针对第一个小问,我们从乙的角度出发考虑问题。

作为乙的智囊团,我们需要向甲提出一系列为难的问题,使得将x可能出现的范围不断缩小。不妨我们把注意力先集中在开始的k+1个问题,我们的目标是使得对应的k+1个可能集的并集最小。

不过多久,就能想到一种二分法的策略。

一开始,x的出现范围是1N中的所有数。那我们的第一个问题就是取出这个集合中一半数量的数问甲,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,乙有必胜策略!

第二个子问题,请听下回分解。