Hamming 码解决帽子问题

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

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

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

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

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

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

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

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

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

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

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

在策略 C 下，错误点构成的集合记作RCRC 。此时，观众成功的概率为1−|RC|/2n1−|RC|/2n .

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

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

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

定理：RC≥2n/(n+1)RC≥2n/(n+1) . 相应的，观众成功的概率不可能大于 n/(n+1)n/(n+1) .

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

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

Q. E. D.