你在这里

集体猜帽问题(3)

主标签

集体猜帽问题(3)

这是一道很有意思题目,最有意思的地方就在于至今为止还没有一个完美的解答,只有一个又一个更加好的解答。

这个问题对于通信中的纠错编码理论有着深远的影响,已经成为每个研究编码理论的人必须要首先研究的一个题目,围绕这个问题所写出的论文也有很多,都不同程度地对整个编码理论产生了影响!

下面是我翻译过来的问题,原文是英文的,感兴趣的可以到我的主页上去看:

有这样一个游戏,游戏的规则是这样的,若干个人为一组,依次走进一个房间,在进入房间门的时候,会有一个机器自动地给每个人带上一顶帽子,帽子有两种——红色和白色的。机器给每个人戴什么颜色的帽子完全是取决于机器的另外一个装置,这个装置是一个投掷器,其功能就是投掷一个硬币,然后机器根据硬币掉在地上的正反面的情况给进来的人戴上相应颜色的帽子。于是,进屋后,每个人都可以看到其他人头上的帽子的颜色,但看不到自己的。

现在每个人有两中选择:1,猜自己头上帽子的颜色;2、放弃。

如果整个组当中至少有一个人猜对了,而且又没有人猜错,那么整个组就可以得到一笔很高的奖金。但是,只要有一个人猜错了,则什么都没有了!

在整个过程中,不允许成员间有任何形式的交流,如眼神、手势..等等,而且每个人无论是做出的回答或者放弃,其他人是不知道的,也就是说,每个人都无法根据其他人的回答来判断从而决定自己的回答!

但是,一组人可以事先约定好回答的方法,这是允许的。

好现在问题来了,例如现在有3个人成为了一组,那么他们应该怎样,才能使获得奖金的可能性(概率)最大呢?

当然,上面的问题还比较简单,但是,当一个小组的人数达到7的时候,问题就变得很复杂了,希望高手们来解答(可能要用到数学上的东西)

 

 

 

 

 

 

集体猜帽问题(3)答案:

经过几个晚上的苦思冥想,我想我终于找到解决那个Hat问题的方法了!

最大的体会是——创造Hamming码的人真是了不起!!实在佩服!!!确实要用到Hamming码方面东西啊,我现在已经找到了7个人时的解决方法,并用程序采取穷举法证明了它的正确性。但可惜的是我无法从数学上证明它,所以虽然我几乎可以肯定这个方法对于所有(2的n次方-1)个人的情况都适用,但我无法用数学证明,我只是用穷举法检验了n=3的时候的正确性。

举n=3,也就是7个人的例子:

在叙述整个方法之前,先把7位情况下的Hamming码列举出来,共16种,如下:

假设7位码各位的名称分别为a6、a5、a4、a3、a2、a1、a0,

        a6 a5 a4 a3 a2 a1 a0 

        --------------------

        0 |0 |0 |0 |0 |0 |0

        0 |0 |0 |1 |0 |1 |1

        0 |0 |1 |0 |1 |0 |1

        0 |0 |1 |1 |1 |1 |0

        0 |1 |0 |0 |1 |1 |0

        0 |1 |0 |1 |1 |0 |1

        0 |1 |1 |0 |0 |1 |1

        0 |1 |1 |1 |0 |0 |0

        1 |0 |0 |0 |1 |1 |1

        1 |0 |0 |1 |1 |0 |0

        1 |0 |1 |0 |0 |1 |0

        1 |0 |1 |1 |0 |0 |1

        1 |1 |0 |0 |0 |0 |1

        1 |1 |0 |1 |0 |1 |0

        1 |1 |1 |0 |1 |0 |0

        1 |1 |1 |1 |1 |1 |1

希望上面没抄错。呵呵..

a6、a5、a4和a3在Hamming码中实际上对应的是信息位,而a2、a1、a0对应的是监督位。换句话说,就是4位信息码和3位纠错码的组合。这些我就不多写了,有兴趣的找相关书看吧。

之所以列出来,是因为后面的方法中是要用到举例说明的。

好了,该隆重介绍我的方法了,呵呵..我的方法是这样的:

首先,定义两种颜色的帽子分别对应数字1和0,这样比较好叙述,假定红色—1,白色—0。

7个人依次进入房间,被戴上帽子,然后他们站成一排,每个人都可以看到其他6人的帽子颜色,于是,关键步骤到了——每个人依次把自己当作Hamming码中的a6、a5、a4、a3、a2、a1和a0,每个人都要这么做。同时每个人手里都拿着一份象我上面一样的Hamming码的编码表,于是,每个人将其他人的组合情况与表中16组编码相应位置的组合情况去对照,如果发现在表中的16组码当中,出现了在某一组编码当中除去自己位以外的其他所有位都与自己旁边的6个人的组合一样,那好,他找到表中的那组编码,查看自己所对应的位在那一组编码中是什么,如果是0,则这个人就猜自己是1,反之,如果表中的a6是1,则他猜自己是0。如果这个人在整个表中都找不到有哪一组符合上述情况,那么这个人就放弃回答。

下面举例说明:

例如,7个人A、B、C、D、E、F、G进入房间,假设他们的帽子颜色分别是“红白红红白红红”,对应成1和0就是“1011011”

好,7个人依次站成一排,即,A的左边是B,B的左边是C,C的左边是D,...F的左边是G。

接着,分别把A、B、C、D、E、F、G看作a6、a5、a4、a3、a2、a1、a0。

于是A把B、C、D、E、F、G的组合“011011”分别与上面表中16组码中的a5、a4、a3、a2、a1、a0相对比,最后,他发现他找不到完全一样的,于是A放弃;

B把A、C、D、E、F、G的组合“111011”与上表中16组码的a6、a4、a3、a2、a1、a0相比较,看有无一样的,可惜,也没有,所以B也放弃。

依次类推,可以推出A、B、C、D、E、G都找不到一样的,于是他们都放弃。

惟独F例外,让我们看看他的情况吧,他将A、B、C、D、E、G的组合“101101”与上面码组中的a6、a5、a4、a3、a2、a0相对比,发现第12组编码“1011001”满足要求,于是F找到这组编码中自己对应位置a1的数字,发现是0,所以F便猜自己是1,也就说自己的帽子是“红”的。

按照上面这个方法,可以得出结论,只有当ABCDEFG的组合出现与上面表中16组码中的某一组完全一样的时候,才会出现所有人都猜错从而失败的情况,而对于其他的情况,则总会成功!7个人所戴帽子总共有2*2*2*2*2*2*2=128种可能,所以失败的可能性是16/128=1/8,也就是说成功的可能性是7/8=87.5%

看了上面这个例子,大家对我的方法都应该有所了解了吧,但我相信,你们的疑问也紧接着就来了:

问题1:你怎么能保证对于任意一个7位的组合,总会有某个人发现其他6人的组合与表中某条编码相应位置的数字完全一样?

对于这个问题,很遗憾,我无法用数学来证明他,但我用程序证明了!而且程序还证明了,每次成功的时候,只有1个人回答对了,而其他6人都是放弃的!关于这点,倒是不难证明,只要根据Hamming码的码间距离为3(用通俗的话说,就是任意两组码,都有3位数不同)就可以知道了。而当失败的时候,是7个人都回答错!也就是说,如果把所有128种情况都遍历一下,你会惊奇的发现,所有回答正确和回答错误的人是一样多的!

所以,如果你能从数学上证明的话,那是再好不过了!

问题2:为什么会想到用这种方法?

呵呵。。。如果让我凭空想的话,恐怕想破脑袋也想不出,好在原文作者虽然没有提供解答的方法,但提示了思路,所以我从一开始便查阅关于Hamming码的书籍,详细了解它的编码方法,虽然这些对于解决这个问题可能都没有什么用处,但这却是一个整理思路的过程。再加上几个晚上的分析、讨论与思考,才突然之间想到的。关键在于把握一点——要让所有人在失败的时候每个人都答错!这是关键。

问题3:为什么Hamming码可以很好地解决这个问题?

用Hamming码相关的知识可以很好地解决这个Hat问题,而且可以说是现在为止最好的、效率最高的方法。至于为什么它能解决这个问题,我只能说这种编码的创始人Richard Hamming太了不起了,这种编码方法太奇妙了,我无法解释更多,只能赞叹这种编码的神奇。

呵呵....其他一些比较简单的问题我就不在多说了,我估计可能大多是关于编码的,其实Hamming码是很有特点的,通过仔细观察它的编码特点,相信不难解决你们的问题。

  

 

另外,我给你证明为什么任何一种情况下,一定会有人回答(也就是为什么会有人可以对上编码表,从而回答而不是放弃)。

实际情况,实际讨论。还是沿用我们熟悉的编码来回答。改变为编码的时候,问题就变成了对于其他128-16=112种情况,每种情况都有一个汉明码和它距离为1(正是有距离的那位回答正确)。但这要用汉明码的性质,因为汉明码的码间距不小于3。所以,对于每个汉明码,都有7个和它距离为一的编码,并且由于汉明码之间距离不小于3,可知这7个码不会和其他任一个汉明码距离为1(最小为2)。

那么可以得到16*7=112,也就是说,所有剩下的编码都可以找到一个和自己距离为1的汉明码。转回原来的问题,就是那112种情况下,都会有人回答并且只有他自己回答正确。

剩下的还继续探讨编码问题。对于纠错编码不知道你怎么理解,我认为汉明码纠错能力比较强,但开销并不小。因为只要传来的码不是汉明码,就认为应该是和它相近的汉明码,进行纠错(因为传错2个码比传错一个码的概率要大的多,尤其在某些可靠传输的设备上),所以事实上汉明码的纠错比较强,但它的开销大了点。

关于汉明码的距离问题,我也记不清楚了,还请你有时间转告。

最后,关于这种hat问题。不论有多少人,只要我们可以找到合适的编码方法(就是类似汉明码这种),就可以得到答案。知道结果是什么?n/(n+1)当然我们现在还不能认定这就是最好的。

要得到n/(n+1)并不难,只要你的编码能遍历2^n/(n+1),并且码间距离不小于3,就可以。方法就是如你所说,按编码表去对。