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 最终总能给出一个大小不超过 2^k的数集，保证 A 心里想的 x 在这个数集里。这里， B 的问题仍然只能是刚才的那种格式，并且 B 仍然可以任意多次地询问。

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

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

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

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

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