这个题目听说是 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.
