# 5. 犯人猜颜色
描述：有 100 名犯人 站成一列，每人头上戴着一个 红色或蓝色 的帽子，自己看不到自己的帽子颜色，但能看到前面所有人的帽子颜色。
每个犯人只能说 “红色” 或 “蓝色”，从最后面（第 100 个人）开始依次说出自己帽子的颜色。如果猜错，立即被处决。
请设计一个策略，使得 尽可能多的人存活。
# 最优策略：使用奇偶校验
目标：确保 99 人存活，仅第 100 个人（最后面的人）可能被牺牲。
# 策略解析
第 100 个人（最后面的犯人）说出前面 99 顶帽子的“奇偶性”
- 设定一个约定：红色 = 1，蓝色 = 0
- 第 100 个人计算前面 99 个人帽子的“红色帽子总数”是奇数还是偶数，然后：
- 如果总数是 偶数，他说“蓝色”
- 如果总数是 奇数，他说“红色”
- 他自己可能会被牺牲，但这一信息给后面的 99 个人提供了参考。
第 99 个人开始，根据第 100 个人的提示推理自己的帽子颜色
- 第 99 个人 已经知道前面 98 个人的帽子颜色，并且听到了第 100 个人报出的奇偶性。
- 他计算出 如果不包含自己的帽子，前 98 个人的红色帽子数量是否符合第 100 个人报的奇偶性：
- 如果符合，说明自己的帽子是 蓝色
- 如果不符合，说明自己的帽子是 红色
- 他说出正确的颜色，确保存活。
第 98 个人依次类推
- 每个人在听到前一个人报出的帽子颜色后，计算是否还保持 红色帽子数的奇偶性，以此确定自己的颜色。
- 依次进行，直到第 1 个人。
# 最终结果
- 第 100 个人有 50% 概率生还（因为他只能根据奇偶性猜测自己的帽子）。
- 其余 99 个人全部生还（因为他们完全可以通过前人的信息推理出自己的帽子颜色）。
- 总存活人数：99 人或 100 人（最少 99 人存活）。
# 方案总结
- 核心思想：使用 奇偶校验 作为全局信息，让第 100 个人提供 公共信息，后续所有人都可以准确判断自己的帽子颜色。
- 牺牲最少人数：最坏情况下 仅第 100 个人可能被处决，而其他 99 个人必定存活。
- 适用于更大规模的犯人：即使是 N 个人，此策略仍然有效，最多牺牲 1 人。
# 相关面试题
- 如果允许说除“红色/蓝色”外的其他话，是否能保证 100% 存活？
- 如果犯人们可以事先协商多种策略，是否能减少风险？
- 如果帽子有 3 种颜色，该策略如何扩展？
这道题考察了 信息编码、数学推理、团队策略，是经典的博弈论问题。
