知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 09 - 帽子颜色 ## 题目 N 个人站成一列,每个人戴一顶帽子(黑或白)。每个人能看到前面**所有人**的帽子颜色(即排在自己前面的所有人),但看不到自己的。主持人从**最后一个人**开始向前依次问:"你的帽子是什么颜色?"每个人必须回答"黑"或"白"。 问:如果允许他们事先商量好策略,**至少多少人能猜对自己的帽子颜色**? ## 大白话理解 你和 9 个朋友被抓去玩一个奇怪的游戏:站成一排,每人被随机戴上黑帽或白帽。你只能看到排在你前面的人的帽子,看不到自己的。当主持人从最后一个人(能看到前面 9 人)开始问颜色时,你必须回答"黑"或"白"。 ``` 站队方式(← 从后往前看): 1号(最前面)→ 2号 → 3号 → ... → 9号 → 10号(最后面,主持问的第一个人) 10 号能看到 1~9 号所有人的帽子 9 号能看到 1~8 号所有人的帽子 ... 2 号能看到 1 号的帽子 1 号谁也看不到 关键:回答是公开的,后面的人能听到前面人的回答! ``` --- ### 核心策略:奇偶性编码 ``` 约定: 黑帽 = 1,白帽 = 0 策略: 第一个人(10号,最后面):数前面所有人中黑帽的数量, 如果黑帽数是奇数 → 说"黑"(这表示"前面黑帽数为奇") 如果黑帽数是偶数 → 说"白"(这表示"前面黑帽数为偶") 注意:第一个人说的"黑/白"不是猜他自己的帽色, 而是向前面的人传递"奇偶性"信息! 第一个人自己对错不重要。 后续的人(9~1号): 听到第一个人报的信息(奇偶性) 再看到前面人的黑帽数量(加上前面人猜对并已经报出的) → 用异或/奇偶性反推出自己的帽子颜色 ``` --- ### 推导过程 ``` 约定:黑 = 1,白 = 0 设帽子序列:C₁, C₂, C₃, ..., C₉, C₁₀ 第 10 号看到 C₁~C₉,计算: P = C₁ ⊕ C₂ ⊕ ... ⊕ C₉ (异或和 = 黑帽数量的奇偶性) 报出 P(但用"黑/白"说出来) 第 9 号听到 P(第 10 号的回答),看到 C₁~C₈: 已知 P = C₁ ⊕ C₂ ⊕ ... ⊕ C₉ 所以 C₉ = P ⊕ C₁ ⊕ ... ⊕ C₈ → 第 9 号能算出自己的帽子! 第 8 号听到 P,看到 C₁~C₇,还听到第 9 号的回答(C₉): 已知 P = C₁ ⊕ C₂ ⊕ ... ⊕ C₉ → C₈ = P ⊕ C₁ ⊕ ... ⊕ C₇ 等等,第 8 号不需要重新算,只需要: C₈ = P ⊕ C₁ ⊕ ... ⊕ C₇ 而 P ⊕ C₁ ⊕ ... ⊕ C₈ ⊕ C₉ = 0(异或加自己等于 0) 所以 C₈ = P ⊕ C₁ ⊕ ... ⊕ C₇(前面看到的) = P ⊕ (前面看到的异或) ``` ``` 更直观的理解(不用异或): 假设第 10 号报:"前面有奇数个黑帽"(可能说"黑") 第 9 号看到了 1~8 号所有人的帽子: → 数一下 1~8 号中有几个黑帽 → 如果奇偶性和 10 号报的一样 → 9 号自己是白帽(不加不减奇偶性) → 如果奇偶性和 10 号报的不一样 → 9 号自己是黑帽(加了 1 改变了奇偶性) 第 8 号: → 数 1~7 号黑帽数,第 9 号帽色已经知道了(公开报出) → 总黑帽数(1~9) = 黑帽数(1~7) + 第9号帽色 → 和自己知道的比较 → 推出自己的! ``` ### 具体例子 ``` 假设帽子:白 黑 白 黑 黑 白 黑 白 黑 白 编码: 0 1 0 1 1 0 1 0 1 0 1号 2号 3号 4号 5号 6号 7号 8号 9号 10号 →→→→→→→→→→→→→→→→→→→→→→→→→→→→→→→→→→→→→→ ← 10 号看到前面 1~9 号 ← 第 10 号:看到 C₁~C₉ = 0,1,0,1,1,0,1,0,1 黑帽 = 1,4,5,7,9 → 5 个黑帽(奇数) 报:"黑"(代表奇偶性 = 奇数) 第 9 号:听到 10 号说"黑"=奇数 看到 C₁~C₈ = 0,1,0,1,1,0,1,0 黑帽 = 2,4,5,7 → 4 个黑帽(偶数) 前面偶 + 自己是黑 = 奇数(与报的一致)→ 自己是黑帽 ✓ 第 8 号:前面 C₁~C₇ = 0,1,0,1,1,0,1 → 4 个黑帽 第 9 号已确定是黑帽(1) C₁~C₉ 黑帽 = 4 + 1 = 5(奇数) 与 10 号报的一致 → 自己必须是白帽(不影响奇偶) ✓ ...依次类推,从 9 号到 2 号都能猜对 ✓ 最后第 1 号也能推出来(前面没有人在他后面了)✓ ``` ### 结果 ``` 第 10 号(第一个回答者):不一定对(他的回答是信号,实际运气好也能对) 第 9 号 ~ 第 1 号(共 N-1 人):全对! 答:至少 N-1 人能猜对。 如果第一个人运气好也能猜对,可以 N 人全对。 ``` --- ### 延伸变体 ``` 变体 1:N 种颜色的帽子(不限于黑白) 用模 N 代替奇偶,第一个人报"前面所有颜色编号之和 mod N" 其他人同样可以反推。 变体 2:不能说话,只能拍肩膀 如果只能用拍肩膀传递一个 bit 信息,策略一样。 拍左肩 = 前面黑帽数为奇,拍右肩 = 偶。 变体 3:帽子随机但必须全部猜对 这不可能——信息量不足。每个人猜对的概率是 1/2, 全对概率 = 1/2^N。 但如果允许第一个人报编码,可以有 N-1 人确定猜对。 ``` --- ## 一句话总结 第一个人牺牲自己的正确率,用奇偶性编码传递给后面所有人。后面的人根据"公开信息 + 自己看到的前面帽子 + 第一位传来的奇偶信号"反推自己的帽色——信息论中的"利用 1 bit 信息传递 N-1 bit 知识"。 --- 下一篇:[10 - 抢30游戏](./10-game-nim.md)
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入