CWYAlpha

Just another WordPress.com site

Thought this was cool: IMO2012趣题:带有说谎的猜数游戏

leave a comment »


    考虑一个传统的猜数游戏。 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 时,对数进行分组并在集合层面套用这种方法,ç

from Matrix67: My Blog: http://www.matrix67.com/blog/archives/5036

Written by cwyalpha

八月 15, 2012 在 5:39 上午

发表在 Uncategorized

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s

%d 博主赞过: