IMO2012趣题:带有说谎的猜数游戏

    考虑一个传统的猜数游戏。 A 、 B 两名玩家事先约定一个正整数 N ,然后 A 在心里想一个不超过 N 的正整数 x , B 则需要通过向 A 提问来猜出 A 心里想的数。 B 的问题只有唯一的格式:先列出一些数,然后问 A “x 是否在这些数里”, A 则需要如实回答“是”或者“否”。显然, B 是保证能猜到 x 的,只需要依次询问“x 是否等于 1 ”,“x 是否等于 2 ”即可。由于 B 可以精心选出满足某种特征的所有数,询问 x 是否在这些数里,因而 B 还可以做得更好。例如当 N = 16 时, B 第一次可以问“x 是否小于等于 8 ”,或者等价地,“x 是否属于 {1, 2, 3, 4, 5, 6, 7, 8} ”;接下来,根据 A 的回复继续细问“x 是否小于等于 4 ”或者“x 是否小于等于 12 ”,以此类推。另一种方法则是询问“x 的二进制表达的第一位是否是 1”,“x 的二进制表达的第二位是否是 1”,以此类推,从而获得 x 的二进制表达的所有数位,便能推出 x 来。

    现在,有意思的问题来了。假设 A 可以偶尔说谎(但保证不会连续说谎两次),那么 B 还能通过询问猜出 A 所想的数吗?如果愿意的话, B 可以询问任意多次。


    看上去 B 的机会似乎不小。考虑到任意两个连续问题中,至少有一个回答是真的,因而不断重复提问似乎是一个不错的策略。不过细想一下你会发现不行,因为 A 可以交替回答“是”、“否”、“是”、“否”,让 B 完全辨不出真假。事实上,即使 N = 2 , B 也无法保证猜出 A 心里想的数。不管 B 怎样问问题, A 总能巧妙地给出回答,保证自己既不会连续两次撒谎,又不会让 B 猜到正确答案。方法如下。每当被问到“x 是否属于 {1, 2}”时,永远答“是”。每当被问到“x 是否等于 1”时,根据前一个问题来回答:如果前一个问题也是“x 是否等于 1”,则给出和前一次相反的答案,前一次说“是”这次就说“否”,前一次说“否”这次就说“是”;如果前一个问题是“x 是否等于 2”,则给出和前一次相同的回答,前一次说“是”这次还说“是”,前一次说“否”这次还说“否”;如果前一个问题是“x 是否属于 {1, 2}”,则这次就随便回答。当被问到“x 是否等于 2”时,用类似的处理方法。这样一来,不管 x 实际上是 1 还是 2 ,任意两次回答中都会有至少一个是正确的, B 将得不到任何信息。 A 的策略可以进一步归纳为:这次装作 x = 1 来回答,下次装作 x = 2 来回答,如此反复。由于 x 要么等于 1 要么等于 2 ,因此 A 的连续两次回答中必有一真。这样一来, B 显然会被 A 搞晕,因为 x = 1 和 x = 2 两种情况处于完全对称的地位。

    不过,如果我们允许 B 最后可以猜两个答案(只要其中一个是 x 就算 B 获胜)的话,可以证明 B 是必胜的,不管 N 有多大。当 N ≤ 2 时, B 显然必胜。当 N = 3 时, B 可以首先不断询问“x 是否等于 3”。如果 A 连续两次答“否”,这一定是实话,这样便能排除了 x = 3 的可能性,直接猜 x 等于 1 或者 2 即可。如果 A 答了一个“是”,那么紧接着问“x 是否等于 2”:如果 A 还答“是”,那么这两个问题的答案必有一真, x = 1 就被排除了;如果 A 答“否”,那么 x = 2 就被排除了,否则 A 就连续两次说谎了。不管怎样,我们最终都能排除掉一种情况,猜测剩下的两个数即可。

    当 N > 3 时呢?我们可以把所有可能的数分成三组,分别标号为第 1 组、第 2 组和第 3 组。别忘了,我们可以给出一个任意大的集合,问“x 是否属于这个集合”,因而我们能套用刚才的方法,把“x 是否等于 3”改成“x 是否属于第 3 组数”,把“x 是否等于 2”改成“x 是否属于第 2 组数”,于是便能排除掉一组数了。不断把剩下的数分成三组,不断套用该方法,直到最后剩下的数不足三个为止。这样, B 便能保证自己的最终猜测是正确的了。


    上述讨论来自于刚刚结束的 2012 年 IMO 第三题。原题的结论更加一般:如果 A 最多能够连续撒谎 k 次(任意 k + 1 次回答中都有至少一次说真话),那么不管 N 有多大, B 最终总能给出一个大小不超过 2k 的数集,保证 A 心里想的 x 在这个数集里。这里, B 的问题仍然只能是刚才的那种格式,并且 B 仍然可以任意多次地询问。

    为了解决这个问题,我们着重考虑 N = 2k + 1 的情况,给出一种通过一系列询问排除其中一个数的方案。当 N > 2k + 1 时,对数进行分组并在集合层面套用这种方法,直到最后所剩的数小于 2k + 1 个为止。

    我们把 x – 1 的二进制表达叫做 x 的“二进制编号”。注意到 x 可以取 1 到 2k + 1 之间的所有正整数,这些数的二进制编号最多 k + 1 位,其中唯一一个恰好拥有 k + 1 位二进制编号的数就是最后的那个数,2k + 1,其二进制编号为 100…000 ,1 后面 k 个 0 。我们假设其他所有数的二进制编号也都恰好是 k + 1 位,不足的话在前面用 0 补足。因此,所有数的二进制编号分别是 000…000 到 100…000 ,每个编号都是 k + 1 位。

    现在,不断问 A “x 的二进制编号的第一位是否是 1”,或者等价地,“x 是否等于 2k + 1”。如果连续 k + 1 次都得到“否”,则直接排除掉 x = 2k + 1 的情况。否则,我们一定得到了一个“是”的回复。紧接着抛出 k 个不同的问题,分别是“x 的二进制编号的第二位是否是 1 ”,“x 的二进制编号的第三位是否是 1 ”,一直到“x 的二进制编号的第 k + 1 位是否是 1 ”。当然,我们需要把这些问题翻译成规定的格式。由于 A 不能连续 k + 1 次撒谎,因此 A 不可能谎报了 x 的二进制编号里的所有数位。所以,我们可以排除掉二进制编号的每一位与 A 宣称的都不相符的那个数。这个数的二进制编号将会以 0 打头(因为 A 说了 x 的二进制编号的第一位是 1 ),因而它确实在 1 到 N 的范围里。

    当 N ≤ 2k 时,直接猜即可;当 N > 2k + 1 时,我们可以用分组排除的方法。因而,对于任意大小的 N , B 都能保证获胜,结论也就证到了。

    上述解法来自于 polymath ,该题还有第二个问,目前似乎仍然没有解答。 polymath 去年也组织了 IMO 试题的讨论,那道题真是神题,见这里

33 条评论

回复给 Sandy tea 取消回复

  +  32  =  42