趣题:猜帽子游戏与Hamming编码

    三个人坐成一个圆圈,每个人头上戴着一顶黑色的或者白色的帽子。每个人都只能看到另外两个人头上的帽子颜色。现在,他们需要独立地猜测自己头上的帽子颜色。每个人都需要在自己的小纸条上写下“黑色”、“白色”或者“放弃”。如果说至少一个人猜对,并且没有人猜错,那他们就获胜了;只要有任何一个人猜错,或者所有人都写的“放弃”,那么他们就输了。如果在游戏开始前他们能够商量一个策略,那么最好的策略是什么?
    仔细想一下你会发现,要想保证他们百分之百地获胜是不可能的,因为游戏中大家不能交流信息,谁也不能保证自己能猜对。但是,有一种策略能保证他们有75%的几率获胜。事实上,当人数n=2^k-1时,我们有一种方法可以让获胜的概率达到(2^k-1)/(2^k)。你能想到这种策略吗?

    设身处地地想,你会想到一个很自然的策略:如果一个人看到另外两个人的帽子颜色一黑一白,那这个人就放弃(换了你你也不敢猜);如果另外两个人的帽子颜色一样,那你就猜相反的颜色(概率上看也要大些)。我们来看一下在哪些情况下使用这样的策略能够获胜:

3个黑帽子:每个人都看到两个黑帽子,每个人都猜自己是白帽子,所有人都猜错;
2个黑帽子,1个白帽子:戴黑帽子的人看到一黑一白,于是放弃;戴白帽子的人看的是两个黑帽子,因此他将猜对,从而所有人都获胜;
2个白帽子,1个黑帽子:和上面这种情况是类似的,所有人都将获胜;
3个白帽子:和第一种情况是类似的,所有人都猜错。

    注意到只有在第一种情况和第四种情况下才会输掉游戏,这两种情况占了所有情况的2/8。于是,使用这种策略有75%的概率获胜。

    我们需要想一想,在这个看似几乎不可能获胜的游戏中,为什么这种策略会有如此高的获胜概率。最关键的就是,这种策略充分利用了胜负判断的准则:大家要错就一起错,只有一个人错怪划不来的;要获胜就只让一个人猜对,多几个人同时猜对也没用。

    根据上面的讨论,我们开始尝试把游戏的人数推广到一般的n。为了叙述方便,我们把每个人头顶上的帽子颜色依次用0和1来表示,数字1表示黑帽子,数字0表示白帽子。于是所有可能的情况就是2^n个01串。游戏开始前n个人预先约定一些“保留串”。他们的策略就是,观察其余n-1个人的帽子颜色:如果和所有的保留串都不匹配里,则放弃;如果恰好符合某个保留串,就猜自己是相反的颜色。比如,当n=3时,他们可以约定两个保留串000和111。如果实际情况是001的话,前两个人看到的是?01和0?1,不属于任何一个保留串,于是放弃;第三个人看到的是00?,正好和000相符,于是他就反过来猜自己不是那个0。注意到一些有趣的事实:如果实际情况恰好就是这些保留串之一,那大家就全猜错了;如果实际情况与所有保留串都相差两个数字以上,那大家全部放弃;如果实际情况与某个保留串恰好差一个数字,那只有一个人猜对,其余人放弃,从而获得胜利。现在的问题就是,如何寻找一个保留串集合,使得和某个保留串只差一个数字的情况尽可能的多。注意,我们必须要保证,任意两个保留串之间不能只差一个数字,这样的话才能保证发现有相符保留串的人不会面临“两可”的情况。假如你找到了t个保留串,则保证获胜的情况最多有t*n个(每个串“变一位”都有n种方法)。显然,最完美的情况就是t+t*n恰好等于总的情况数2^n。当n=2^k-1时,t+t*n是有可能恰好等于总情况数2^n的,也就是说每种可能的情况要么就是一个保留串,要么与唯一的一个保留串恰好差一位。此时,t+t*n=t(n+1)=t*(2^k)=2^(2^k-1),t应该等于2^(2^k-1-k)。下面我们说明这t个保留串是如何生成的。
    每个保留串都由原码和校验码两部分组成。我们把n位01串的位置编号转化为二进制,二进制里只有一个数字1的位置(即左起第1,2,4,8,…位)叫做校验码,有至少两个1的位置(3,5,6,7,9,…等其余位置)上的数字称作原码。显然,原码应该有n-k位(即2^k-1-k位)。枚举2^(n-k)种原码的01组合,对于每一组原码,定义第i个校验码的值为,除了它本身以外,所有编号的二进制表达中右起第i个数字为“1”的位置上一共有奇数个1还是偶数个1(相当于把标“x”的位置上的数异或一遍)。比如,第2个校验码是1,当且仅当有奇数个位置上的原码满足,位置编号的二进制表达形如…???1?且该位置上的数值正好也是1。所有可能的原码加上它对应校验码就是我们的保留串。

  01串:     a1  a2  a3  a4  a5  a6  a7
十进制编号:  1   2   3   4   5   6   7

二进制编号: 001 010 011 100 101 110 111
校验码1(a1):         x       x       x
校验码2(a2):         x           x   x
校验码3(a4):                 x   x   x
保留串0:     0   0   0   0   0   0   0
保留串1:     1   1   0   1   0   0   1
保留串2:     0   1   0   1   0   1   0
保留串3:     1   0   0   0   0   1   1
保留串4:     1   0   0   1   1   0   0
   ……      ……     ……        
保留串14:    0   0   1   0   1   1   0
保留串15:    1   1   1   1   1   1   1

    我们可以说明,对于任一个n位01串,只要它不是我们的保留串,我都有办法只变动一个数字让原码和校验码相符(从而变成一个保留串)。我们可以观察一下,由原码算出来的校验码和实际的校验码有哪些不同。如果只有一位校验码不同,直接把它改过来就是了;如果有多位校验码不同,那就找出改动哪一位原码可以让这些校验码同时取反。从位置编号的二进制的角度来考虑,这样的一位原码显然是唯一存在的。同时,我们可以保证任两个

8 条评论

发表评论

  +  58  =  68