欺诈猜数游戏(上)

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