帽子游戏一

系列：头脑风暴
查看该系列所有文章

在这个游戏的开头，我们设想自己要参加一个电视游戏大奖赛。规则呢，是这样。我们有 n 个人，作为一个小组来参加游戏。游戏中，主持人会给我们每人头上戴一顶帽子。帽子有黑白两种颜色，可以认为它们在我们各自头上的分布是临时随机决定的。小组中的每一个人，可以看到其他人的帽子颜色，但不知道自己的帽子颜色。每个游戏成员都被要求回答自己帽子的颜色。我们各人面前有三个按钮，可以选择“黑色”“白色”或“弃权”(也就是 pass，不作猜测的意思)。小组成员彼此之间没有任何信息交流，他们必须各自独立地作出自己的选择，并且谁也不知道其他人的选择。如果小组成员全部选择了 pass，也就是每个人都弃权，则他们输了；如果有小组成员作出了明确的猜测，但某个人猜错了，则结果也是输。只有当小组中有人做出猜测，并且每个做出猜测的人都猜对了，他们才能获胜，一起获得最后的大奖。

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

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

在这里用Hamming码给出了问题在 $n=2^k-1$ 时候的一种解释和策略，成功概率为 $1-1/2^k$ 。但这个问题为什么最后归结于Hamming码，这种方法为什么是最优的呢？这里再讨论一下。

模型：帽子的黑白状态为一个n长的串，可以用一个n维的超立方体G的顶点坐标 $(x_1,$ , $x_2, \cdots, x_n)$ 来表示，坐标为0表示白帽子，1表示黑帽子。G上两顶点相邻当且仅当它们之间仅相差一位，这样每个顶点恰与n个点相邻。

目标：主持人在G上随机选取一个顶点P，第i个观众知道这个顶点除第i个之外的n-1个坐标值，给出一种回答策略，使得所有问答的观众都答对了正确的P。

这个问题的关键是怎么把“策略”模型化。

注意到在游戏中，每个人他能观测n-1个坐标值，也就是他能够确定P为G上某条边 $(u, v)$ 的两个顶点之一。他在游戏中的策略具体表现为，当他观测到这条边时，他选择这条边的哪个顶点，或者不做选择。

如果观测到 $(u, v)$ ，策略选择了 $u$ ，则在G上连一条有向边 $u\rightarrow v$ 。

策略：一个策略C可以表示为G的某些边的有向化。

引理：如果P点处出度（即P连出的边数）等于0——没有人回答错误，且入度（连向P的边数）大于0——至少有一人回答，则当主持人选择P点，观众获胜。否则观众失败。

在策略C下，错误点构成的集合记作 $R_C$ 。此时，观众成功的概率为 $1-|R_C|/2^n$ .

定义：图G(V,E)上，V的子集D称为G的Dominating Set当且仅当G的任何顶点要么在D中，要么与D的某个顶点相邻。

定理：G的顶点集 $R$ 为某个策略C的错误点集 $R_C$ 当且仅当 $R$ 为G（无向图下）的Dominating Set。其中 $C=\{u\rightarrow v: u\in R, (u, v)\in E(G)\}$ 。

对于一般图，求Dominating Set是NP完全问题。对于这个超立方体而言，一方面有下界：

定理： $R_C \geq 2^n/(n+1)$ . 相应的，观众成功的概率不可能大于 $n/(n+1)$ .

而在 $n=2^k-1$ 时，上面的等号可以取到，构造 $2^{2^k-k-1}$ 个 $2^k-1$ 长度的01串，任何两个之间的距离大于2（即为纠错度为1的纠错码）。

讨论：如果帽子颜色有三种，又该如何？

Pingback: 帽子游戏二 @ 阅微堂
Joyce on 2007-06-27 at 11:24 said:

发现个小错误：
“如果P点处出度（即P连出的边数）等于0——没有人回答错误，且出度（连向P的边数）大于0”
应为
如果P点处出度（即P连出的边数）等于0——没有人回答错误，且入度（连向P的边数）大于0
zhiqiang on 2007-06-27 at 12:25 said:

已改正。多谢提醒。
Dai Liang on 2007-12-14 at 14:06 said:

不太明白
条码 on 2009-12-17 at 09:51 said:

似乎很有意思。。。但是有点高深，非一般人能看懂。。。
wangsincos on 2010-04-27 at 20:49 said:

博主您好！
这个问题很好，它极大地激起了我的兴趣。
我研究了很长时间，但得到的结果和您给出的不大一样：
例如当n=7时，我算出的最优值是85/128，并且我证明出这个数也是n=7时的上限
请问博主可够构造出一个策略，使得n=7时赢的概率是7/8(或者大于85/128)
非常感谢！！
还有，能否告诉我这个问题的出处（我希望做一些类似的题来提高思维能力）
zhiqiang on 2010-04-28 at 17:21 said:

题目中的那个将一个策略表示为一个图是等价的，要找7/8的策略，先找一个图，然后反推回去即可。
wangsincos on 2010-04-28 at 20:19 said:

在这里分享一下我的想法
这个问题我是这么想的：
首先，我们必须明确“策略”是什么形式的。我们把这n个人排成一队：

p1, p2, p3, ..., pn.一个比较广义的策略是确定n*2^(n-1)*3个参数：某

一个人(pi,n个人)当他看到的其他n-1个人帽子颜色的某一种情况时(2^(n

-1)种情况)回答0，1，？的概率(记黑帽子1，白帽子0，弃权？)。

我们引进一种表示法：
n=3时
如果当1看到23分别为01时,1弃权的概率为1/4
那么我们把这个记作f[X01, ?] = 1/4

例如，n=3时，我们的策略可以是这样的：

f[X00, 0] = f[X00, 1] = f[X00, ?] = 1 / 3
f[X01, 0] = f[X01, 1] = f[X01, ?] = 1 / 3
f[X10, 0] = f[X10, 1] = f[X10, ?] = 1 / 3
f[X11, 0] = f[X11, 1] = 1 / 4, f[X11, ?] = 1 / 2

上面的四行相当于确定了p1的策略
即当第一个人看到第二三个人帽子颜色分别为白白、白黑或黑白时，他都

会等概率随机从三个选项中抽一个，而当第一个人发现第二三个人的帽子

都是黑色的时候，他会有1/4的概率回答0, 1/4的概率回答1, 1/2的概率回

答？

前面的解释，仅在于举一个例子说明什么是一个策略。
我们还可以形式化这个问题：
确定所有的f[S, c], S是一个长度为n的01串并且其中有一位被X所取代(当

然这个X如果出现在第i位则表示这个状态是第i个人所见到的),c是0，1，

？中的一个

好，我们现在开始正式讨论这个问题：
当这n个人开始游戏时，会产生2^n*3^n种不同的情况，2^n个帽子情况和与

每种帽子情况对应的3^n种不同的回答(当然有可能某一些回答是不存在的

，即f值为0)
某个策略所对应的胜率就是将这6^n种情况中可使获胜的情形进行概率的累

加。

我们可以发现，作为最优策略，每一个f的值一定是0或1(观察"策略所对应

的胜率",利用介质定理)，或者更严谨地说，一定存在一个最优策略，使得

每一个f的值非0即1
这意味这什么呢？我们只需确定每个人面对某个特定情况时选择哪个选项

，而不需要研究“在不确定中的不确定”

另一方面，我又发现在某一个确定的帽子分配后，如果有两个人a,b看到的

黑帽个数如果是一样多，那么我们就应该让这两个人的回答一致，因为这

样做不会使得情况变坏(如果这两个人回答的是一黑一白，那么我们一定可

以改成全黑或全白；如果是?和0，我们就可以把?变成0)
上面的结论意为着什么呢？我们只需确定n个选择来完成这个策略!即如果

某人看到i个黑帽子后所做的选择。记g[i]来表示此时的选择(0<=i<=n-1)

实际上，可能的帽子分配方案数不是2^n, 而是n+1!!只不过在基本事件中

所占的个数不同罢了，它们所占的比例是按组合数C(n,i)那样分配的

这样，当我们知道g后我们只需要对这n+1个事件分别进行判断
我们用[statement]来表示statement的布尔值
0个黑的成功(s[0]) 的充要条件是[g0 = 0]
s[1] : [g0 0][g1 1][g1g2 ??]
s[2] : [g1 0][g2 1][g1g2 ??]
.
.
.
s[n-2] : [g[n-3] 0][g[n-2] 1][g[n-3]g[n-2] ??]
s[n-1] : [g[n-2] 0][g[n-1] 1][g[n-2]g[n-1] ??]
s[n] : [g[n-1] = 1]

对于特定的g, 答案是Sigma[0<=i<=n]C(n,i)s[i]/2^n
这个最优值怎么求呢？
当然可以用动态规划的方法O(n)求出(将C(n,i)的时间看成O(1))

但这是一个数学问题，我们还需要继续研究下去
我们把注意力放在s这个n+1维向量的取值上，会发现一个惊人的性质：不

能有连续三个s的值全是1， s[0]=1时s[1]1, s[n]=1时s[n-1]1.此外

，对于s，我们也一定能构造出合法的g
于是这个问题又惊人的转化成了下面的问题：
一个数列C(n,0), C(n,1), C(n,2),...,C(n,n-1),C(n,n)
选取若干项，使得没有连续三项是连续的，并且第一项和第二项不能同时

选，最后一项和倒数第二项同时选。
这个问题可以用贪心的方法解决，考虑到组合数的性质
最后通过对n模6的讨论，我列出了连加式（可惜没有找到和的闭形式）

例如当n = 7时
1 7 21 35 35 21 7 1
我们从这两个候选中选一个和最大的
7 35 35 7
1 21 35 21 7
为85

所以n = 7时最好是85/128

难免有一些问题，欢迎讨论
zhiqiang on 2010-04-28 at 21:04 said:

你有两个关键引理：

1、每个人的选择都是确定的
2、一个人的选择“可以”只依赖于它看到的黑帽子数量。

前者是对的。后一个不对。你仔细研读一下我写的文章。这个帽子问题严格等价于多维立方体上的Dominate Set问题。
Shisen on 2012-03-24 at 02:50 said:

新接触这个博客，从以前的文章中学到了很多知识，谢谢！用 $\LaTeX$ 编码写出来效果并非想象中那样，暂时没能搞清楚怎么回事，对系统有限制么？这次的留言中数学公式难看了一点，见谅！

只要上界的话可以有更初等一点的办法。比如考虑一个矩阵， n 列（n 为人数）， 2^n 行. 每一列对应一个人，每一行对应一种帽子的带法。矩阵的每一项是0,1 或者－1：

对于每一种帽子的带法（编号为 i），如果第 j 个人作出正确的判断，那么矩阵的（i, j）位置就写 1, 错误判断就写 -1, 不判断就写 0.

由于每个人判断的方法跟他自己带的帽子的颜色是无关的，所以不管是什么策略，这个矩阵的每一列加起来都是0, 所以矩阵所有项的和是0.
我们也可以先求每一行的和。假设使大家获胜的帽子带法的编号集合是 W, 使大家输的带法编号集合是 L，那么 |W|+|L|=2^n.
对于固定的一行，行和是答对的人数－答错的人数，所以对于 i \in W, 第 i 行的和最少是 1. 而对于 i \in L, 行和最少是－n. 所以这个矩阵所有项的和 >=|W|-n|L| >= |W|-n (2^n - |W|) = (n+1)|W|-n*2^n. 所以
|W| <= (n*2^n)/(n+1), 所以获胜的概率最多不超过 n/(n+1).

当然这个论证没能给出具体策略。如果有k种不同的帽子的颜色的话，那么类似的论证可以给出一个粗略的上界， [n/(n+1)]*2/k.
zhiqiang on 2012-03-24 at 09:24 said:

你这个很好很初等。你是数学竞赛选手吗？

你能在详细说说多种帽子颜色的想法不。我觉得咱俩的方法有共通之处，你看看能不能把我的方法推广到多种颜色，从而能获得一个构造性的证明？

关于LaTeX数学公式，你可以参考一下这里。比如用$\LaTeX$可以打出 $\LaTeX$ 。注意公式不能有中文字符，反斜号和括号必须使用英文半角字符(特征是显示宽度只有汉字的一半)。
Shisen on 2012-03-25 at 05:54 said:

直接点Reply回复总是不成功，我的机器怎么这么奇葩。。。
我用同样的字符打出来效果是 $\LaTeX$ 还好这次不需要打严肃的数学公式。我用的mac的机器，下次需要打公式的时候换台机器试一下。
我以前是在中科大念的数学本科，现在在美国康奈尔大学念数学博士，近来有想法毕业之后改行做quant, 所以去mitbbs quant 版转了一下，看到有人贴了你的 “何时适可而止”的文章链接，所以就跟进来看了一下，发现有好多好东西啊。。。偶然。。。
关于k种帽子的情形，我发现之前粗心了，再推一下发现只能得到上界 n/(n+k-1)，对不起。具体步骤如下：
矩阵还是那个矩阵， k^n行， n列。用 P 表示矩阵中 1 的总个数，用 N表示矩阵中-1的总个数。由于每个人做的决定和他自己的帽子颜色是无关的，所以对于每种他猜对的情形，必然对应 k-1种他猜错的情形，所以有: N=(k-1)P.
由于每个使大家胜利的行，至少有一个1 ，所以 |W|= N.
把以上的不等式串联起来，就有 n|L| >= N=(k-1)P >= (k-1)|W|.
所以 |W|/|L| <= n/(k-1).
所以胜利的概率最多不超过 n/(n+k-1).
感觉这个界太松了，很难实现：要么所以人都猜错，要么正好只有一个人猜错，其他人都不猜。
你的方法我看过觉得很有意思，但是并不觉得很构造性啊，想要合适的策略图不用汉明码怎么弄？
zhiqiang on 2012-03-25 at 09:50 said:

抱歉，你的这三条留言被弄到审核名单里去了，原因未知。

我文章里写的方法就是构造性证明，原因在于证明了错误点级的特征（即一个Dominating Set）。当知道这个特征后，剩下的用Hamming码是自然而言的事情。
jiawei on 2012-04-06 at 20:37 said:

由于每个人判断的方法跟他自己带的帽子的颜色是无关的，所以不管是什么策略，这个矩阵的每一列加起来都是0, 所以矩阵所有项的和是0.

......没看懂，可以解释下为什么每一列的和为0，是期望吗？
zhiqiang on 2012-04-08 at 15:12 said:

Shisen可能没看到你的问题，我替他回答一下吧。

首先你问的应该是两种颜色的情况。这时候，每一列对应一个参与者。对给定的一列（和这个参与者），这个参与者只能看到这一行的其它n-1个列，而在这一列有两种可能性，0和1。所以这2^n行可以分成2^(n-1)对，参与者是区分不出来这一对里的哪一行。如果参与者选择不回答，此时两行上该列都是0；如果回答的话，其中一行答对了（值为1），另外一行答错了（值为-1）。无论哪一种情况，每两行的和都是0。