帽子游戏二

作者:
系列:头脑风暴

查看该系列所有文章

这个题目听说是 MSRA 的面试题。

在这个游戏的开头,我们设想自己要参加一个电视游戏大奖赛。规则呢,是这样。我们有 n 个人,作为一个小组来参加游戏。游戏中,主持人会给我们每人头上戴一顶帽子。帽子有黑白两种颜色,可以认为它们在我们各自头上的分布是临时随机决定的。小组中的每一个人,可以看到其他人的帽子颜色,但不知道自己的帽子颜色。每个游戏成员都被要求回答自己帽子的颜色(且必须回答,而且是独立回答的)。只有当所有人都回答正确(注意这里与 帽子游戏一 的区别),他们才能获胜,一起获得最后的大奖。

这个游戏还有最关键的一点:在游戏开始前(帽子戴上之前),有一个「协商时间」,小组成员可以聚在一起,讨论决定小组应采取什么样的策略。但这个交流过程在游戏开始时自然终止。

现在的问题是:小组选择什么样的策略,才有最大的机会获胜呢?

因为任何一个人没有关于自己的帽子的任何信息,所以正确率不可能超过 1/2。关键是怎么让所有人要么同时正确,以达到这个 1/2 的正确率。

所以,正确的策略应该是每个观众回答其余所有观众的帽子的异或( 0 表示白帽子, 1 表示黑帽子,则第 i 个人回答 \( \oplus_{j\not=i}^n x_j\)

OK ,现在这个问题到这里已经完整了。但令人惊奇的是,在两个星期前,来自伦敦大学的 Taoyang Wu 给了一个非常有趣的讲座,上面这个游戏恰是这个讲座的一个特例。

上面的问题其实是说有一个完全的有向图,每个顶点上有一个随机的变量。每一个点都知道它的邻居(连向它的点)的变量,需要猜测自己的信息。问以怎么样的策略能够使得所有点同时正确的概率最大?

显然,这个概率(记作 \( p(G)\) )与这个图 G 的结构密切相关,这样, \( p(G)\) 某种意义上是这个图的结构的一个度量,称为 Guessing Number ,等于 \( g(G)=n+\log p(G)\) 。根据前面所说,完全图的 Guessing Number 为 n-1。另易知一个单环的 Guessing Number 等于 1。而对一般图 Guessing Number 问题,无论是从直接求解(猜测是 NP-hard ),还是其性质分析,都还留下很多未解决的问题。

Q. E. D.

系列: 头脑风暴 »
有 n 只狮子,要吃一头鹿。狮子按照聪明程度从 1 排到 n。最聪明的狮子可以选择吃掉鹿,可如果它吃掉鹿的话,它就变蠢了,就有可能会被第二的狮子吃掉。可如果第二头狮子吃掉第一头狮子,它又可能会被第三头狮子吃掉,这样一次下去...
前两天贴出了一个 硬币游戏 ,希望寻找一种胜利策略。这是一个非常有意思的题目,没事做的时候可以用来锻炼思考能力。我迫不及待的想在这里公布解答,因为我已经把它解决掉了。如果有人还想继续享受思考的乐趣,请飘至 原问题
在这个游戏的开头,我们设想自己要参加一个电视游戏大奖赛。规则呢,是这样。我们有 n 个人,作为一个小组来参加游戏。游戏中,主持人会给我们每人头上戴一顶帽子。帽子有黑白两种颜色,可以认为它们在我们各自头上的分布是临时随机决定的。小组中的每一个人,可以看到其他人的帽子颜色,但不知道自己的帽子颜色。每个游戏成员都被要求回答自己帽子的颜色。我们各人面前有三个按钮,可以选择「黑色」「白色」或「弃权」(也就是 pass ,不作猜测的意思)。小组成员彼此之间没有任何信息交流,他们必须各自独立地作出自己的选择,并且谁也不知道其他人的选择。如果小组成员全部选择了 pass ,也就是每个人都弃权,则他们输了;如果有小组成员作出了明确的猜测,但某个人猜错了,则结果也是输。只有当小组中有人做出猜测,并且每个做出猜测的人都猜对了,他们才能获胜,一起获得最后的大奖。
我很早之前就想过这个问题,但一直只知道一个 trivial 的答案。前两天无意中发现网上已经有高手给出了更好的方案,故记录在此。有兴趣的可以自己想一想。