欺诈猜数游戏(上)

上个月在新加坡的时候,正值国际生物奥林匹克竞赛在新加坡国立大学举行。于是不免想去看看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\),则乙获胜;否则甲获胜。证明:

  1. 若\(n\geq 2^k\),则乙可保证获胜;
  2. 对所有充分大的整数\(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\),乙有必胜策略!

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

21 (this post is made with love)

Leave a Reply