Hamming Code 和囚犯帽子问题

实在是忙，只能随便写几句交差。_:'(

问题。有十五个囚犯，每个囚犯随机的戴上了一顶黑帽子或白帽子，黑白概率各为1/2，而且十五顶帽子的颜色是互相独立的。这十五个囚徒都知道别人帽子的颜色，不知道自己的。

现在每个囚犯可以猜自己帽子的颜色，也可以选择不猜。如果至少有一个人猜了，并且没有人猜错，就释放他们，否则统统杀头。

他们可以事先商量一个策略，戴上帽子之后就不能再交流信息。

是否存在一个策略，使得他们被释放的概率超过90%?

解答要用到所谓 Hamming Code。

Hamming code 是用来减少传递信息中的错误的。大致的原理是这样：假设有 2^n-1-n 个 bits 的信息要传递，我们就传 2^n-1 个 bits，要传的信息放在不等于2^k的位上，等于2^k的位用作 parity。例如要传11个bits的信息 01100101110,把这个数放在15个bits里面，成为__0_110_0101110，然后计算 parity, 有1的位上是0100010，有2的位上为0101010，有4的1101110，有8的是0101110。最后送去的是010111000101110。这样编码的特点是任意两个对码的距离至少为2，所以如果收到了一个错码，（假设只错了一位，）很容易就能还原成对码：只要把parity不对的位加起来就可以了。例如010101000101110，1和4 parity 不对，第5为是错码。

当总位数是2^n-1时，Hamming code 另外有一个性质：所有的对码和错码覆盖了所有2^n-1位的数。这个性质对我们的囚徒问题更重要。这15个囚徒可以商量一个顺序。每个囚徒知道别人的颜色后，把颜色按顺序写成二进位数。然后把自己的颜色带进去，形成两个15位的二进位数。如果两个都是错码，不猜。如果一对一错，猜错的一个。如果帽子的颜色形成一个对码，（概率为1/16，）所有人都会猜，而且都猜错。如果是错码，（概率15/16，）只有一个人（错码所在位数的人）会猜，并且猜对。

所有跟帖： 

• 计算 parity没看懂 -redrick- ♂ (193 bytes) () 06/19/2007 postreply 23:33:33

• 回复：计算 parity没看懂 -康MM- ♀ (334 bytes) () 06/20/2007 postreply 13:49:22

• 这下明白了，非常感谢 ^_^ -redrick- ♂ (0 bytes) () 06/20/2007 postreply 23:19:01

• 嗯，咔咔 -redrick- ♂ (750 bytes) () 06/21/2007 postreply 03:03:03

• 回复：Hamming Code 和囚犯帽子问题 -gamemaker- ♂ (60 bytes) () 06/30/2007 postreply 12:27:29

• 付程序 -gamemaker- ♂ (2925 bytes) () 06/30/2007 postreply 12:35:08