白帽子问题.md

白帽子问题

问题：

在一个房间里有100个学生。每个人头上都戴了一顶帽子，帽子的颜色是白色或者黑色。每个学生都只能看见别人的帽子的颜色，而不能看到自己帽子的颜色。

老师对所有人说：“你们每个人要么戴白帽子，要么戴黑帽子，并且有人戴白帽子，请戴白帽子的同学举手。” 如果没人举手，老师一分钟后再问：“请戴白帽子的同学举手。” 然后老师每个一分钟后重复同样的问题，直到所有戴白帽子的学生都举手为止。

假设每个学生都极其聪明，100个学生中只有5个人戴了白帽子。请问，什么时候戴白帽子的学生会全部举手？

共同知识：

为了解答的时候说的更清楚明白，先来认识一个概念叫做共同知识。其实共同知识就是某一件事情，所有人都知道，所有人都知道所有人都知道，所有人都知道所有人都知道所有人都知道……

Common knowledge is a special kind of knowledge for a group of agents. There is common knowledge of p in a group of agents G when all the agents in G know p, they all know that they know p, they all know that they all know that they know p, and so on ad infinitum. —— Wikipedia

解答：

共同知识的概念有点绕，不过我们一边解题一边来慢慢体会。

第0轮 — 老师说有人戴白帽子

共同知识：有人戴白帽子

第1轮 — 第一次让白帽子举手

分析：如果只有一个人（叫他A）戴白帽子，那么从 A 的视角来看，其他人都戴黑帽子。结合第0轮共同知识，那么戴白帽子的只能是 A 自己，于是他将会举手。但是事实是，由于有 5 顶白帽子，所以上述情况不可能发生。所以第1轮没有人举手。

结果：没有人举手

共同知识：在分析过程中，我们排除了一种可能，就是只有一个人戴白帽子。因为第1轮没有人举手，所以大家现在都知道，不只一个人戴了白帽子，并且所有人都知道其他人知道。所以现在的共同知识是：有大于等于 2 个人戴白帽子。

第2轮 — 第二次让白帽子举手

分析：假设只有两个人（假设其中一个人为 A）戴白帽子，那么从 A 的视角来看，其他人总共戴了一顶白帽子。基于第1轮的公共知识，他能够判断自己必定戴了白帽子，否则将只有一顶白帽子，与之前的公共知识矛盾。但是事实是，由于有 5 顶白帽子，所以上述情况不可能发生。所以第2轮没有人举手。

结果：没有人举手

共同知识：在分析过程中，我们排除了一种可能，就是只有两个人戴白帽子。因为第2轮没有人举手，所以大家现在都知道，不只两个人戴了白帽子，并且所有人都知道其他人知道。所以现在的共同知识是：有大于等于 3 个人戴白帽子。

第3轮 — 第三次让白帽子举手

分析：同理可得，如果只有三个人戴白帽子，那么他们才都会举手。

结果：没有人举手

共同知识：有大于等于 4 个人戴白帽子。

第4轮 — 第四次让白帽子举手

分析：同理可得，如果只有四个人戴白帽子，那么他们才都会举手。

结果：没有人举手

共同知识：有大于等于 5 个人戴白帽子。

第5轮 — 第五次让白帽子举手

分析：每一个戴白帽子的人都只能看到其他四顶白帽子，而基于上一轮共同知识，每个戴白帽子的人都能判断出自己戴了白帽子这个事实。

结果：每个戴白帽子的人都同时举手。

公式：

一共有 N 个人戴白帽子，那么第 N 次提问让白帽子举手的时候，所有白帽子同时举手。

拓展：

下面这道网上流传的 Google 面试题，也就是类似的思路。

有个小镇有100对夫妇，每个丈夫都在欺骗他的妻子。妻子们都无法识破自己丈夫的谎言，但是她们却能知道其他任何一个男人是否在撒谎。镇上的法律规定不准通奸，妻子一旦证明丈夫不忠就应该立刻杀死他，镇上所有妇女都必须严格遵守这项法律。有一天，镇上突然来了一个陌生人，他宣称至少有一个丈夫是不忠的。那么接下来会发生什么呢？