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,這一點也不好笑,如果你還沒有聽說過用帽子顏色表示思考類型的故事,那你一定太年輕)。

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

Comments

Popular posts from this blog

如何評估推薦系統(一)

備忘:在 Mac OS 環境安裝 Python 開發工具

[詩戀] 鄭愁予/定