百囚猜帽

奇異果

某監獄里有100位囚犯，他們即將被執行死刑，但恰逢那天是國王的生日，國王打算給他們一次赦免的機會。

100位囚犯坐成一列，每人戴上一頂白色帽子或者黑色帽子。坐在最后面的囚犯能夠看到前面99位囚犯所戴的帽子顏色，而坐在最前面的那位囚犯看不到其他人的帽子顏色。接著，看守會從后往前依次叫這些囚犯猜測自己頭頂上的帽子顏色。如果哪位囚犯猜對了，他就自由了。對了，別人猜測的時候其他人都能聽見。除此之外，一旦開始猜測，他們不可以有任何交流。

瞎猜？顯然這是不可取的策略，因為每個人猜對的可能性只有二分之一，這太冒險了。于是，囚犯們聚集在一起商量策略，想辦法讓猜對的人數最多。

無從下手，嘗試簡化

假設現在只有囚犯A和B，A在第一個位置，而B在第二個位置。那么，他們可以使用這樣的策略：B先猜A的帽子顏色，A聽到B猜什么顏色就猜什么顏色。這樣就能保證A的猜測是對的，不過B只有50%的概率猜對。

倘若增加到3位囚犯，我們看看有沒有辦法保證至少有2位囚犯猜對。

假設3位囚犯從前到后依次是A、B、C，C猜B的帽子顏色，然后B猜，而A收不到任何有用信息，他只能瞎猜，這樣只能保證B是對的。顯然，2位囚犯的策略已不再適用3位囚犯的情況，需要更換策略。可不可以根據奇偶性來進行猜測呢？

如果C看到A和B共有奇數頂白色帽子，就猜“白色”;如果C觀察到A和B共有偶數頂白色帽子，就猜“黑色”。等C猜完后，那么B就知道他和A是有奇數頂白色帽子還是偶數頂白色帽子，然后他再看A戴的是白色帽子還是黑色帽子，就可以確定自己的帽子顏色了。對于A來說，他知道自己和B戴的白色帽子總數的奇偶性，也知道B戴的是白色帽子還是黑色帽子，那么他就能輕而易舉地推測出自己頭頂上的帽子顏色了。

從上面的分析中，我們知道該策略保證了A和B都能猜對自己頭頂上的帽子顏色，而C有50%的概率猜對。

舉實例，分步驗證

理論上，根據顏色、帽子數量來猜測的策略是可行的。但將其運用到實際中，是否可行呢？我們來看看。

不妨假設3位囚犯和其所戴的帽子顏色如下表：

關于策略有這樣的規則：

1.最后一位囚犯計算前面所有白色帽子的數量。如果是奇數，他就猜“白色”;如果是偶數，他就猜“黑色”。

2.除了最后一位囚犯，其他囚犯全部優先自保。

下面，囚犯們開始執行策略。

第三位囚犯，他看到了一頂白色帽子和一頂黑色帽子。也就是說，白色帽子數量為奇數，所以他猜“白色”。

第二位囚犯，他聽到了“白色”，也就知道了白色帽子有奇數頂，而自己看到一頂白色帽子。所以，他知道自己頭頂上的帽子為黑色，于是他猜“黑色”。

第一位囚犯，他知道了白色帽子有奇數頂，又聽到第二位囚犯猜了“黑色”。所以，他知道自己頭頂上的帽子為白色，于是他猜“白色”。

由上表可知，該策略能保證至少有2位囚犯猜對帽子顏色，也就是說策略可行。

人數增多，同樣適用

人數增多，策略還是否適用呢？我們將這種策略推廣到100位囚犯身上——如果最后一位囚犯看到前面所有囚犯有奇數頂白色帽子，就猜“白色”，否則猜“黑色”，然后前一位囚犯觀察他前面的囚犯所戴白色帽子的數量，做減法就能知道自己頭頂上的帽子顏色了，以此類推。

假設現在最后一位囚犯數出前面一共有52頂白色帽子，于是他猜“黑色”。沒人知道他的帽子顏色，所以他只有50%的存活可能。但他猜的“黑色”卻給前面的人提供了許多幫助。

到倒數第二位囚犯，他也數了前面98位囚犯戴的白色帽子的數量。如果數出偶數，他就猜“黑色”;如果數出奇數，他就猜“白色”。也就是說，如果倒數第二位囚犯數出前面有52頂白色帽子，那么他就能推出自己戴的是黑色帽子;如果他數出前面有51頂白色帽子，那么他就能推出自己戴的是白色帽子。這樣他既救了自己，又為前面的人提供了可靠的信息，一舉兩得。

依次下去，至少99位囚犯可以被釋放。這種策略顯然是可行的，不過對于最后一位囚犯來說，他猜對猜錯全靠運氣了。