Hat Problem: why you should care ?

這是一篇舊聞了，是紐約時報 2001年4月10日，科學版上的一篇文章。但是剛在 Digg 上發現，看到有超過七百人次「頂」這篇 Why Mathematicians Now Care About Their Hat Color，連上紐約時報仔細拜讀，才真正認識了這個不簡單的策略遊戲。

遊戲規則

數學界一般認為猜帽子顏色的遊戲是由 Dr. Todd Ebert (DBLP)在1998年，他的博士論文中提出來的。

這是一個團隊參與的遊戲，參與人數從三人到更多人都可以，遊戲的勝負是以整個團隊的結果來決定結果。在遊戲過程中，參與者每人頭上都戴著紅色或藍色的帽子，參與者只能看到別人的帽子顏色，但是不能看到自己的帽子顏色。每個參與者必須猜測自己頭上帽子的顏色，參與者之間不能有任何形式的溝通，只能觀察別人的帽子，然後猜測自己的頭頂是什麼顏色。

猜測的選項有三個，紅色、藍色或棄權（pass），如果覺得自己無法下決定，可以選擇 PASS。當參與團隊中每個有作出猜測的人（棄權的人就不管了）的猜測結果都正確，則這個團體可以獲得獎金。

依照遊戲規則，在觀察和猜測時，遊戲玩家間不得有任何溝通行為，但是在遊戲開始前，這個團隊可以作「策略」討論，遊戲開始後，所有成員根據大家事先協商的策略，來決定自己的行動（猜測或放棄）。這個遊戲的核心就是 ：有沒有一個「贏的策略」？這個策略的成功機率有多高？

三個人的策略

以最簡單的三人情況來說，三個人都是紅色或藍色的機率各是八分之一，所以有四分之三(扣掉全藍及全紅的情況)的機會，是兩個人的帽子顏色相同，第三個人是另外一種顏色。因此有個可能比較容易贏的策略，每個參與者觀察另外兩個人的帽子顏色，如果這兩個人的帽子顏色不同，則猜測者選擇放棄；如果另兩個人的帽子顏色相同，猜測者猜自己的帽子是另外一種顏色。

雖然當三個人的帽子顏色相同時，以上辦法是絕對沒有機會贏的， 不過這是參與者數目為三人的最佳解決方案（optimal solution），以下是從網路上找到的證明。

Each guess has a 50-50 chance of being correct. This means that when we consider possible outcomes there must be an equal number of correct and incorrect guesses. Notice that in each win there is a single correct guess and in each loss there are three incorrect guesses. Winning one more game requires one more correct guess (a total of 7), but now we have only 1 possible game to lose and 7 incorrect guesses to make. There are only 3 players so this is impossible.

By Brody Dylan Johnson at Saint Louis University

更多人的狀況

網路上有許多人改編這個遊戲，改變帽子的顏色，參與的人數，從電視遊戲大獎賽到囚犯問答，但是問題的本質仍然相同，這些不同的描述方式，可以在網路上找到（例如 New York Times, ABC News, Die Ziet）。

三個人的遊戲，只是這個遊戲的基本版。超過三個人的狀況，讓事情變得複雜許多。有人認為這是典型的 Game Theory 問題，也有人思索這個問題的 social 版本，但是也有人認為這一個數學模式（Model）的問題，有數學家「認真」的去找答案，真的在編碼理論（Coding Theory）中找到解決問題的方向。

Dr. Hendrik Lenstra, a professor of mathematics at Berkeley, and Dr. Gadiel Seroussi, director of information theory research at HP Labs, have developed a new type of covering code to define an even better strategy for large numbers of players.

以上的解法，使用編碼理論中的 Hamming Code，來描述問題，這種作法在參與人數是2的次方數減一(例如 3, 7, 或 15 )的時候幾乎無懈可擊，但是其他的狀況就不是那麼容易處理。而且數學家還無法證明這個解決方案是否為最佳解(optimal)。還有一點值得一提，這個問題的重要關鍵在於「團隊」，只有整個團隊都正確，才能贏得這個遊戲。所以，除了數學模式之外，我們還有多少種可能的觀點？這是更有趣的問題。

Googling the Hat Problem

在寫這篇短文的時候，使用 Google 作了一個簡單的小研究。發現在網路上除了英文的資料外，竟然有許多簡體中文的討論群組或網站，提到這個帽子問題，倒是繁體中文的資料少之有少。這個觀察結果，可能比起帽子問題，還要有趣，或者說更讓人頭痛。

或許我們可以提出幾個猜測，大陸網站的內容，屬與原創製作的比例是令人存疑的，所以這麼多的帽子資料，究竟是否能代表他們熱愛這類益智問題，是令人存疑的。而繁體中文資料的貧乏，則是我們這個環境的網路文化的縮影，究竟這是什麼意思，我不知道。

不管這個觀察結果，是否隱喻我們不喜歡動腦筋。不過，我很好奇老外為何喜歡以帽子作為思考或比喻的輔助，數學家擔心帽子的顏色，搞企管的人則用帽子教人如何作個好主管（No，這一點也不好笑，如果你還沒有聽說過用帽子顏色表示思考類型的故事，那你一定太年輕）。

唯一的結論是，台灣人比較(不)愛戴帽子(不，我沒有談政治)...