如何知道自己有沒有戴綠帽子

這是一個經典的低笑點段子，相信大多數人稍稍思考片刻，就可以恍然大悟：對於侍者的問題，三個人只要有一個人答案為否，整個問題的答案就是否，第一個邏輯學家如果自己心裡想要啤酒，但是不知道其他兩個人的意向，只能回答不知道，相反，如果他自己心裡不想要啤酒，就可以直接回答否，不用再看其他兩個人的意向。第二個邏輯學家也是類似的情形，不知道第三個邏輯學家的意向，只能回答不知道。輪到了第三個邏輯學家，他從前兩個邏輯學家的回答中已經可以判斷出前兩個人都要啤酒，而他自己也要啤酒，於是最終才給出侍者的問題的答案："是的！"。

其實此類的邏輯遊戲還有很多更好玩的，跟"戴綠帽子"有關係的那些邏輯故事就很有趣。

【圖片出處：http://9thcivic.com/】

版本1

假設在監獄裡有一百個囚犯，他們即將被執行死刑，不過在最後時刻，執行官給了他們一次活命的機會。執行官讓一百個囚犯前後站成一排，然後給每個人帶上一頂帽子，帽子是紅色或者綠色的，兩種帽子的可能性各有一半，每個囚犯都看不到自己頭上帽子的顏色。然後執行官掏出槍來，從站在排尾的那個囚犯開始，"一個一個過篩子"，逐一要求每個囚犯說出一種顏色，紅色或者綠色，如果說對了就可以絕處逢生，如果說錯了，砰一聲，立刻槍口對準腦袋一槍解決。執行官還強調："你們回答我問題的時候，只准說紅色或者綠色，說任何多餘的話立刻就地正法。"看來在這個遊戲中，有沒有帶綠帽子可是事關生死的大事情。

表面上看起來，在這種情況下，每個囚犯雖然能看到自己前面的人帽子的顏色，卻看不到自己頭頂上的帽子是紅色還是綠色的，只能亂猜一個，聽天由命了，平均100個人里能有50個活下來。有人會說如果每個人說帽子顏色的時候都說前面一個人的帽子的顏色，暗中起了提醒作用，情況會不會好一些？對於排位的最後一個人來說，這樣做無妨，可以讓倒數第二個人知道自己帽子的顏色。不管之後排尾那個人被崩掉了還是活下來，輪到倒數第二個人的時候，他已經在心裡知道自己帽子的顏色（比如紅色），如果他前面的人，也就是倒數第三個人的帽子也是紅色，他喊一聲紅色既可以救自己的命，就可以通知前面的人。可是如果事情走向另外一半的可能：倒數第三個人的帽子是綠色，對於倒數第二個人來說，捨己為人或者舍人為己，讓自己活就不能提醒前面的人，提醒前面的人自己就沒命了。事實上，即使每個人都捨己為人提醒前面的人，總的生還比例並不會增加。

100名囚犯除了接受以扔硬幣的方式死亡以外，有沒有更好的辦法呢？當然有，而且可以保證100個人里有多達99.5個人活命，而不是50個。

99個是指除了排尾最後一個人以外的99個人，0.5個人是指排尾的那個最不幸的傢伙也有1/2的可能性活命。

辦法是這樣：所有的囚犯要團隊合作。規則1：從倒數第一個人開始，數一下前面的所有人戴綠帽子的個數是奇數還是偶數，如果是奇數，就說綠色；如果是偶數，就說紅色。規則2：從倒數第二個人開始，在思考自己應該說的顏色同時，還要仔細聽一下前面的人說過的顏色，如果一共有奇數個人說過綠色，就改變自己按照規則1原本要說的顏色；否則正常說出規則1的顏色就可以。

只要按照這樣，每個人既可以說出自己頭頂帽子的顏色，還可以為前面的同伴提供信息，那個執行官只好無奈的放走所有的犯人。

舉個例子：假設一共四個囚犯，從後向前，紅帽子，綠帽子，紅帽子，綠帽子，倒數第一個囚犯看到前面有偶數個綠帽子（2個），說紅色，自己可以活命；倒數第二個人看到前面有奇數個綠帽子（1個），後面0個人說過綠色，於是喊綠色，也活命了；正數第二個人看到前面有奇數個綠帽子（1個），本應喊綠色，但是後面有1個人喊過綠色，於是喊紅色，也可以得救；輪到最前面的那個囚犯，前面綠帽子為0，本應喊紅色，但是同樣因為前面有人喊過一次綠色，改喊綠色，也和自己帽子顏色一致。最後四個人都可以生還。

如果遊戲不是一長排從後向前逐個人說出帽子的顏色，而是所有人在同一個瞬間說出，而且所有人要死一起死，要活一起活。具體是這樣的，每個人可以選擇說紅色，綠色或者沉默不語，但是必須保證沒有人說錯自己頭頂帽子的顏色，而且至少有一個人說對自己頭頂帽子的顏色，才算過關（也就是說所有人如果都保持沉默照樣要被槍決），所有人都可以活命，否則後果你懂得。

在這種情況下每個人都不可能在瞬間知道自己頭頂上有沒有綠帽子，似乎也無計可施了吧，這回真的要看運氣了吧。其實並不是這樣的，我們假設最簡單的情況，一共只有三個囚犯，可以有一種策略保證他們在75%的時候可以活命。

方法很簡單，三個囚犯在同時猜的時候按照這樣的規則：如果看到另外兩個人帽子顏色不一樣，保持沉默，如果另外兩個人帽子的顏色都是紅色，喊綠色；如果另外兩個人帽子顏色都是綠色，喊紅色。

三個人A，B，C的帽子顏色組合一共有下面這八種：

按照以上的策略，在所有的八種情況的六種下，三個苦逼的囚犯都可以保住性命。這似乎有點和概率相違背，因為無論怎麼猜，是同時進行的，每個人都不知道自己頭頂帽子的真正顏色，對於確定的某一個人來說，假設說綠色，自己頭頂的帽子是紅色和綠色的可能性各佔50%，這意味著在一種情況下的正確的答案，在另外一種相反的情況下就是錯誤的答案。

按照規則每次只要有一個人說對，其他兩個人沉默就可以完成任務，要是八種情況下有六種情況脫險，需要一共有六次說對，但同時也意味著在其他情況下有六次說錯。我們可以設法"編碼"，把說錯的6次都集中在一起，在剩餘的兩種情況中（全是紅色，全是綠色）一錯到底。這正是以上提到策略的初衷，在75%的時候保證每次有一人說對，在剩下25%的時候讓每個人都說錯，這樣總的說錯次數和說對次數相等，但是生還的概率卻遠超過一半。事實上，對於3個人的情況，75%概率也已經是可能的最好結果。

如果遊戲有更多的囚犯參加，他們一起生還的機會還可以更高，如果有N = 2^n – 1 個人參加, 他們使用最佳的策略活命的機會將是N/(N + 1) = (2^n – 1)/2^n，如果7個囚犯參加，活命的機率將是87.5%，如果15個囚犯參加，活命的機率將是15/16=93.75%。

7個人玩遊戲的時候道理還是同樣的，他們帽子顏色的組合將會一共有2^7=128種可能性，在這128中裡面我們最多可以保證有112種情況下有一個人才對，其他人全部沉默不語；然後在剩下的16種情況下，所有人全部去猜，而且全猜錯，16*7=112，猜錯的次數和猜對的次數還是相等的，不與概率計算相違背。不過策略具體執行起來就不是用一兩句話就能說清楚的了，需要首先給七個囚犯用二進位遍上號000,001一直到111，然後每個囚犯在決定是不是要喊，喊紅色還是綠色的時候，要根據其他人帽子的顏色和對應的編號，進行二進位的計算，應用的是通信上的Hamming Code糾錯碼方式，詳情可以參看：

http://www.math.vt.edu/people/brown/doc/dozen_hats.pdf

雖然計算複雜了一點，但是可以保證所有的人以最大的概率活命，也算值了，當然如果囚犯都不是邏輯學家和程序猿，數學沒死理性派這麼好，估計活命有點難。