＜第１章＞Ｎ维座标：
Ｎ个人有Ｎ顶帽，就像Ｎ维座标；每个帽子非黑即白，非０即１。
(a1, a2, a3, a4, a5 ... an)
ai 非0即1 ，这是所有可能的帽子颜色组合。
我们以 Ｎ=11 为例，如：(1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0)，进行以下的说明。
＜第２章＞使用汉明码，实现一位数字的检错纠错：
汉明码的作法是每逢 2^n 位 （1, 2, 4, 8, 16, 32...）的位置，就塞入一个检验码；至於其余的位数，则填入资料本身。
举例：
我们将原本的 11 个数字 (1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0)
改写成为 15 个数字 (A, B, 1, C, 0, 0, 1, D, 0, 1, 1, 0, 0, 1, 0)
可以看见 A,B,C,D 是我们后来塞进第 2^n 位（1, 2, 4, 8）的四个检验码，而其他 11 个数字则照顺序递延。
A, B, C, D 的值是 0 还是 1 呢？很简单，我们使用下面的公式将 15 个数字转换成为二进位（A,B,C,D 暂时不计算），然后进行 XOR 运算：
1 * A =
2 * B =
3 * 1 = 0011
4 * C =
5 * 0 = 0000
6 * 0 = 0000
7 * 1 = 0111
8 * D =
9 * 0 = 0000
10 * 1 = 1010
11 * 1 = 1011
12 * 0 = 0000
13 * 0 = 0000
14 * 1 = 1110
15 * 0 = 0000 XOR
-------------------------
1011
接下来，我们的目标是将 XOR 的答案凑成 0000 ，所以 A,B,D = 1 ，而 C = 0
1 * 1 = 0001 ...A
2 * 1 = 0010 ...B
3 * 1 = 0011
4 * 0 = 0000 ...C
5 * 0 = 0000
6 * 0 = 0000
7 * 1 = 0111
8 * 1 = 1000 ...D
9 * 0 = 0000
10 * 1 = 1010
11 * 1 = 1011
12 * 0 = 0000
13 * 0 = 0000
14 * 1 = 1110
15 * 0 = 0000 XOR
-------------------------
0000
汉明码的好处在於”一位检错”的能力：如果这 15 位数在资料传递途中错了一位，那麼最后 XOR 的计算结果就不是 0000 。
此外，如果 XOR 的结果是 1001 （十进位之中的”9”），我们就知道错的是第 9 位数。
结论１：
只要错误不超过两位数，使用汉明码就可以侦错且纠错。
结论２：
当全码（资料＋检错码）长度为 (2^k)-1 位时：
其中 k 位是检错码
其中 (2^k)-1-k 位是资料
以上面为例：
ABCD 4 位数是检错码
剩下 11 位是资料
请注意”结论１”，假设某一个二元数列合乎汉明码检测（XOR 结果0000...）的话，那麼你随便改动任何一位数，都会导致它不合乎汉明码检测。
故，任两个合乎汉明码检测的二元数列，都至少有两位数以上不同，用标准术语来讲，这两个数列的【汉明距离】大於等於 2 。
再依据”结论２”，我们知道如果总数列长度为 2^k - 1 时，其中有 k 位是检错码（检错码的值并不自由、是由数据决定的），剩下 2^k - 1 - k 位是数据（可以是任意 0, 1 组合）－－换句话说，如果总数列长度为 2^k - 1 时，你可以构造出 2^(2^k - 1 - k) 个不同的、且合乎汉明码检测的数列－－这个结论异常重要！
＜第３章＞证明本题：
假设你有Ｎ顶帽子，写成Ｎ维座标是 (1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0) －－其中 1 代表白帽，0 代表黑帽。
所有 0,1 组合，就是游戏主持人可能给大家戴的帽子，这形成了一个Ｎ维的立方体：每 1 个点都有 N 个邻居（你把任何一位数的 0 变 1 或 1 变 0 ，就形成一个邻居，所以每个点都有Ｎ个邻居）。
每一个人看不见自己头上的帽子，因此每一个人都要在两个点（设 p1, p2）之间作猜测；而很明显的，p1 与 p2 是Ｎ维立方体的一条边，因为 p1 与 p2 只有一个轴的值不一样，其他 N-1 个值都相同。
今天我们的策略就是如下：
＜１＞把Ｎ维立方体的全部 2^N 个点，分为【出点】与【入点】两类。
＜２＞任何一个【入点】，都要有正好一个【出点】作为邻居（两者属於同一条边：p1, p2）。
＜３＞【入点】越多越好，【出点】越少越好。
＜４＞如果任何一个人，看到自己 p1 与 p2 的两个点，正好是一出一入的话，那麼他就猜【入点】；否则就不要猜。
以上，如果裁判所安排的帽子(0,1,1,0,0....)，不幸正好构成了【出点】，那就输了；反之，如果裁判所安排的帽子，正好构成了【入点】的话，那麼必然有一个人（且仅有一个人）看到自己的那一条边是一出一入，这样他就会猜【入点】的情况，导致猜中。
很显然的，【入点】越多越好，【出点】越少越好，所以最经济的方法就是先建立一个【出点】，然后将他所有相邻的点通通设为【入点】。处理完后，将这些点通通从Ｎ维立方体中移除，接下来再处理剩下的其他点。。。
这，就要讲回汉明码了。。。
＜１＞符合汉明码(XOR计算 = 0)的组合，通通当作【出点】。
＜２＞不符合汉明码的组合，也就是相差一位数的组合，通通当作【入点】。
＜３＞依据汉明码”可以纠错一位数”的特性，我们知道每个【入点】，仅仅会对应一个【出点】，绝对不会同时对应到两个【出点】（否则怎麼纠错），也就不会形成浪费。
依据前一章的【结论２】，当 N = 2^k - 1 时，你可以构造出 2^(2^k - 1 - k) 个不同的、且合乎汉明码检测的数列；换句话说你可以构造出 2^(2^k - 1 - k) 个【入点】，而这是最经济的构造法。
故，你猜错的比例
= 入点数量／总数量
= 2^(2^k - 1 - k) / 2^N
= 2^(2^k - 1 - k) / 2^(2^k - 1)
= 2^(-k)
= 1 / 2^k
= 1 / (N+1)
所以说当 N = 2^k - 1 时，参赛者有局部最大的猜对率 N/(N+1) 。
证毕。
好详细的解答
