帽子謎題復雜版

現在來看“100頂帽子謎題”。囚犯們可以亂猜一通，最壞情況下所有人都猜錯，平均而言則會有50個人猜對。但這道題有趣的地方就在于，100個囚犯可以事先商量一種策略，也就是說，站在后面的囚犯可以利用他的答案，給前面的囚犯提供有用的信息。顯然，最后面的囚犯是不可能保證自己猜對的，他猜紅或猜藍，猜對的可能性都只有一半。但囚犯們可以事先約定一種暗號。比如，最后一個囚犯可根據他前面緊挨他的 （倒數第2個）囚犯所戴帽子顏色，報出自己所戴帽子的顏色。也就是說，通過他的答案可以告訴倒數第2個囚犯其所戴帽子的實際顏色，于是倒數第2個囚犯肯定能活下來。此時，倒數第3個囚犯面臨與最后那個囚犯相同的處境，并且以同樣方式保證倒數第4個囚犯存活。這樣下去，可以保證至少50個（倒數偶數號）囚犯存活。而對另50個囚犯來說，答對答錯的可能性是50%，或者說平均會有25人猜對。這樣的話，平均總共有75個囚犯存活。但這不并是最佳策略。最佳策略能保證：除了站在最后面的囚犯之外，其余99個囚犯都能答對。這個最佳策略是什么？親愛的讀者，在你繼續看下去之前，不妨先動動腦子。

前面那種策略的弱點在于，排在最后的那個囚犯透露的信息不多。其實，他完全可以透露出一些與全局相關的信息，讓前面所有的囚犯都可利用這些信息。比如，他可以數一數前面99個人一共有多少頂紅帽子，并約定他猜“紅”表示他前面共有偶數頂紅帽（當然也可作其他約定）。倒數第2個囚犯也數一數他前面98個人的紅帽子數量，如果數出來是奇數，那么他戴的肯定是紅帽子（因為必須加上他戴的紅帽子，才能保證最后那個囚犯所看見的紅帽子數量為偶數）;如果他數出來的是偶數，那么他自己戴的肯定是藍帽子。這樣，倒數第2個囚犯肯定就答對了。那倒數第3人呢？如果倒數第2人說自己戴的是紅帽子（這當然是確切信息），而他（倒數第3人）數到自己前面的紅帽子數為偶數，那如果他自己戴的是藍帽子，就會造成倒數的前99人中紅帽子數為奇數，這與倒數第1個囚犯的準確提示不符合，因此他戴的必定是紅帽子。以此類推，只要記住了后面所有囚犯的答案，再加上對前面囚犯所戴不同顏色帽子數量的奇偶性進行統計，除了排在最后的那個囚犯之外，其他99個囚犯都能答對，也就是都能活下來。這就是最佳策略，不可能再有其他策略能保證所有人都存活。

再把問題變難一點：有10個囚犯和10頂帽子，每個囚犯被隨機戴一頂帽子，要么紅色要么藍色，但囚犯們不知道每種顏色的帽子數量。囚犯們被安排進不同房間，以便讓每個囚犯能看見其他囚犯的帽子，但看不見自己的帽子。他們必須同時說出一個詞——紅或藍。如果說出的詞與自己所戴帽子的顏色相同，這個囚犯就被釋放。如果足夠多的囚犯獲釋，他們就可能回來拯救還未獲釋的囚犯。這些囚犯被允許有1小時的商議時間，如果他們能找到一個合理的策略，則10名囚犯中有5人肯定會獲釋，然后他們就可以回來拯救其他人。那么，這個策略是什么？

答案是：把囚犯們分成對子。在對子AB中，A說出他看到的B的帽子顏色，B則同時說出與他所見A的帽子顏色相反的顏色。這樣，如果AB所戴帽子顏色相同，A獲釋，B不能獲釋。如果AB所戴帽子顏色不同，B獲釋，A不能獲釋。這樣，總共會有5人說對。也可把囚犯們分成5人一組，共兩組。其中一組假定紅帽數量為偶數，另一組則假定為奇數。與前面的100頂帽子情況相似，他們可以根據這一假定推斷出自己所戴帽子的顏色，但只有一組能答對，因此肯定會有5人獲釋。（這后一種思路為什么可行，這里不詳細解釋。請有興趣的讀者自行思考。若想出了正確的推理過程，可發到本刊微信號dazirantansuo，答對者可免費獲得本刊下期新雜志一冊。）

這些謎題的答案看起來都不太復雜。然而，若非學過這方面的知識（大多數人都沒學過），或者絕頂聰明，要想在應聘時一下子就想出這樣的答案顯然很難。其實，完全可以把這些謎題中的10個或100個囚犯換成無窮個，依然能找出最佳策略。不過，這要用到大學數學和邏輯學知識。