Hamming 码解决帽子问题

作者: , 共 1784 字 , 共阅读 0
系列:数学之美

查看该系列所有文章

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

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

Q. E. D.

系列: 数学之美 »
本文将证明:最佳约会策略里提到策略,忽略前 37%的对象,然后在剩下的对象里挑第一个比前 37%都好的对象,这个策略是最优的。更准确地,我们将证明:任何约会策略的成功概率都不可能超过$ \frac{u}{n}\sum_{i=u}^{n-1}\frac1i$ ,其中$ u$ 为满足$ \sum_{i=u}^{n-1}\frac1i\geq 1$ 的最大值。这个$ u$ 大约为 37%,最后成功的概率大约为 40%。
珍爱生命,远离政治。今天我们讨论一个数学问题。
类似文章:
相似度: 0.385
这个题目听说是 MSRA 的面试题。
在 MIT BBS 上看到一个有趣的题目
以前提到过,理论计算机这门课会邀请一些正在这边访问的教授来讲课,由于是本科生,所以这些教授一般都是讲些有趣的东西,比如之前的overhang 堆积木 - 能伸出桌面多远?。今天这次课,来自 Aarhus 的Peter Bro Miltersen讲了一个很有趣的游戏问题。
相似度: 0.093
前两天贴出了一个硬币游戏,希望寻找一种胜利策略。这是一个非常有意思的题目,没事做的时候可以用来锻炼思考能力。我迫不及待的想在这里公布解答,因为我已经把它解决掉了。如果有人还想继续享受思考的乐趣,请飘至原问题
相似度: 0.092
$ n$ 枚硬币排成一排,两人轮流取,每人每次可取其中一枚或者相邻的两枚。
数学 » 数学游戏, 概率
蚁迹寻踪及其他数学探索》提到一个游戏:
数学 » 概率, 数学之美
这个题目是当年北大概率课上陈大岳老师出的练习题目,当时是一个简单情形,球上 4 个点组成的四面体包含球心的概率。最近在 MITBBS 上看到又有人提及。我在这里写一下解答。
本文将证明:最佳约会策略里提到策略,忽略前 37%的对象,然后在剩下的对象里挑第一个比前 37%都好的对象,这个策略是最优的。更准确地,我们将证明:任何约会策略的成功概率都不可能超过$ \frac{u}{n}\sum_{i=u}^{n-1}\frac1i$ ,其中$ u$ 为满足$ \sum_{i=u}^{n-1}\frac1i\geq 1$ 的最大值。这个$ u$ 大约为 37%,最后成功的概率大约为 40%。
相似度: 0.074
注:此游戏很有名,有同学问我其算法,我在网上找了一下,居然没多少中文资料,这里按照以前看过的一份答案回忆整理贴出。
题目来源:《A practical Guide to quantitative finance interviews》,解答和书上的可能不一样。
本文将证明:最佳约会策略里提到策略,忽略前 37%的对象,然后在剩下的对象里挑第一个比前 37%都好的对象,这个策略是最优的。更准确地,我们将证明:任何约会策略的成功概率都不可能超过$ \frac{u}{n}\sum_{i=u}^{n-1}\frac1i$ ,其中$ u$ 为满足$ \sum_{i=u}^{n-1}\frac1i\geq 1$ 的最大值。这个$ u$ 大约为 37%,最后成功的概率大约为 40%。
后一篇:
这个题目听说是 MSRA 的面试题。