微軟面試題：紅帽子與黑帽子
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
總結
對於所有的紅帽子，他們的地位是相同的，也就是視角永遠一樣，對黑帽子也同樣成立，所以如果有信息就會是同時得到，而不是一些人先發現。那這個問題就分紅黑兩類來考慮就行了。這也是屬於博弈論相關的問題，可以先考慮小數據的簡單場景。
本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/zgPXYqSRkdyRqbQ7gmwl0w