100囚犯帽子：约定一个策略，救下99人

题目

100 个囚犯排成一列，每人随机戴黑或白帽子，只能看到前面人的帽子（看不到自己和后面的）。从最后一人开始，依次报出自己帽子的颜色（只能说“黑”或“白”，且所有人都能听到前面的回答）。若报对就活、报错就死。行刑前可约定策略。怎样保证至少 99 人存活？

答案与解析

用**奇偶校验（parity）**传递 1 比特信息：

约定：最后一人（1 号，看到前面 99 顶）数前面黑帽的奇偶性。若黑帽数为奇数，他说“黑”；偶数说“白”。他本人有 50% 概率死，但把“前面 99 顶的奇偶”告诉了所有人。

2 号听到 1 号的话（已知前 99 的奇偶），又亲眼看到前面 98 顶，便能反推出自己帽子的颜色，准确报出。3 号在听到 1 号奇偶、2 号正确自报后，同样能推自己……依此类推，第 2 到第 100 人全部必活，只有 1 号赌命。

背后的数学

这是信息论/编码里“用校验位救全场”的寓言。1 号牺牲自己当 1 个奇偶校验位，后续每人借“已知的总奇偶 − 已确定的前面”推出自己。 generalizes 到 $n$ 人保 $n-1$ 活，也连通了汉明码的纠错思想——用极少的冗余位，锁定大量未知。现实中卫星通信对抗噪声，用的正是同一套哲学。