微软面试题：红帽子与黑帽子

来源丨经授权转自 小K算法（ID：xiaok365）

作者丨小K算法

01故事起源

一群人开舞会，每人都戴着一顶帽子。帽子只有红和黑两种，其中黑的至少有一顶。每个人能看到其它人的帽子颜色，但看不到自己的。

大家先一起做一个游戏，规则如下：
所有人先看别人头上戴的是什么帽子，然后关灯，如果有人认为自己戴的黑帽子，就打自己一个耳光。

游戏开始：

第一次关灯，没有声音。

于是打开灯再看一遍，第二次关灯，依然鸦雀无声。
一直到第三次关灯，才有声音响起。

问：有多少人戴着黑帽子？

02

分析

假设有5个红帽子，和5个黑帽子。

对于红帽子的人，他看到的是有4个红帽子，和5个黑帽子。

对于黑帽子的人，他看到的是有5个红帽子，和4个黑帽子。

那么第一次关灯，对于任何一个人，只能得到上面的信息，他是无法判断自己的帽子颜色的，所以肯定啥也不发生。

03

寻找突破口

题目是问戴黑帽子的有几个人，跟具体人数相关。但我们再回到题目描述，并没有给总共多少人，也没有说红帽子有多少人，只有一个跟数字相关的条件，就是戴黑帽子的至少有一人，这就是突破口。

所以这类的问题都可以从题目的信息量上面寻找突破口。
没有说红帽子有多少人，说明解题的思路肯定跟红帽子没什么关系，有多少都无所谓，那就从黑帽子开始思考。

04

小规模简单场景

4.1

假设只有1个黑帽子

对于每一个红帽子，他看到的场景是这样的。第一次关灯他们都无法确定自己帽子的颜色。

对于唯一的一个黑帽子，他看到的场景是这样的。因为至少有一个黑帽子，他没有看到，所以推出自己一定是黑帽子，第一次关灯声音响起。

4.2

假设有2个黑帽子

对于每一个红帽子，他看到的场景是这样的。第一次关灯他们是无法判断的。

对于2个黑帽子，他看到的场景是这样的。

第一次关灯，他们都在等对方打耳光，所以什么也不会发生。

因为第一次没有声音，这时他俩都知道，第一次对方在等自己打耳光。所以这时他们都可以判断自己是黑帽子，第二次关灯声音响起。

4.3

假设有3个黑帽子

对于红帽子的人来说，一定比黑帽子的人后得到信息，所以不考虑。

对于其中的每一个黑帽子，他们认为2次之后对方可以发现，结果两次之后因为都在等，不会有声音，那第三次都可以判断自己是黑帽子了。

4.4

假设有N个黑帽子

根据上面分析，可以推论第N次声音响起。所以题目第3次有声音，也就意味着有3个黑帽子。

05

总结

对于所有的红帽子，他们的地位是相同的，也就是视角永远一样，对黑帽子也同样成立，所以如果有信息就会是同时得到，而不是一些人先发现。那这个问题就分红黑两类来考虑就行了。这也是属于博弈论相关的问题，可以先考虑小数据的简单场景。

如果喜欢小K的文章，请点个关注，分享给更多的人，小K将持续更新，谢谢啦!

👇👇👇
2021.04.23期活动 开奖啦~~

04 月 23 日，圈儿在《为写论文，华人学者向Linux提交200多条「恶意代码」，结果整个大学都被Linux封了》一文中发起了包邮赠书活动，本次活动已于 04 月 27 日北京时间 16：00 截止，下面圈儿就来公布中奖情况：

书籍中奖者*8：

100积分中奖者*5

请上面 13位 中奖伙伴凭中奖回复留言截图添加圈儿微信号：jb_quaner，领取奖品（3天未领取视为放弃）。如有疑问，也可以添加圈儿微信号咨询哦。

没有中奖的伙伴也不要气馁哦，我们后续还有礼品等待大家的认领~~~

每天 17：30 不见不散！

识别关注我们

了解更多精彩内容

点分享

点点赞

点在看