帽子游戏一

作者:, 发表于

在这个游戏的开头,我们设想自己要参加一个电视游戏大奖赛。规则呢,是这样。我们有 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的纠错码)。

讨论:如果帽子颜色有三种,又该如何?