戴帽子問題

有沒有聽說過「戴帽子問題」？

問題的描述是這樣的：有三頂黑帽與兩頂白帽，自其中挑選三頂，讓 A、B、C 分別戴上一頂後，讓 A 排在 B 之前，B 排在 C 之前，形成一直線。每個人可以看到排在自己前面的人所戴的帽子顏色，但是卻看不到自己或排在自己後面的人所戴的帽子。現在，問 C 是否知道自己的帽子顏色，C 回答「不知」；接著問 B 是否知道自己戴的帽子顏色，B 也回答「不知」。最後，問 A 是否知道自己戴何色的帽子，A 卻回答「知道」。那麼，A 戴的帽子顏色是什麼呢？他又如何推斷出自己的帽色？

就像一般的邏輯問題，我們可以從證明論（Proof Theory；例如從「若 P 則 Q」以及「P」，可推斷出「Q」）或模型論（Model Theory；例如，窮舉所有可能性，然後說明，在所有的狀況下都成立）來著手解決。

一般的解答，都是利用證明論來解釋：
A 自問：我的帽子是白色的嗎？如果是，B 可以推論他自己的帽子是黑色的；因為若 B 的帽子也是白色的，C 就會看見兩頂白帽，從而推斷出自己戴黑色的帽子。然而，B 並沒有推斷出他自己戴什麼顏色的帽子，因此一開始的假設「A 帶白帽」不成立，因此可推斷出「A 帶黑帽」。

這個解答，因為用到數次「反證法」（Proof By Contradiction；用「非 P」為偽來證明「P」為真），因此很容易讓人有「喔，好聰明的解答啊」之感。不過，若換個角度，從模型論的觀點來看，或許可以得到更深刻的直觀：

參考上圖，帶黑帽標示為小寫 b，戴白帽則標示為小寫 w。

首先，我們知道，每個人頭上都帶有一頂帽子，因此 A, B, C 戴的帽子可能性，共有 8 種（參考圖 (1)，每一列是一種可能性）。

但問題又敘述說，黑帽有三頂（或三頂以上），而白帽只有兩頂，因此不可能三人都戴著白帽（參考圖 (2)，我們把三人都戴白帽的狀況用紅線刪除掉）。

接下來，問題又說：「問 C，回答不知自己所戴帽色」。因為 C 可以看見 A, B 所戴的帽子顏色，所以從圖 (2) 可知，A 與 B 不能夠同時戴有白帽（換句話說，A, B 若同時戴有白帽，則從圖 (2) 的第七列，C 可知自己戴著白帽）。所以，我們可以把 A, B 同時戴有白帽的狀況刪除（如圖 (3)）。

然後，問題說，「接著，詢問 B，也不知自己戴那種顏色的帽子」。因為圖 (3) 說明了，若 A 戴白帽，則 B 必然戴著黑色帽子（圖 (3) 的前四列說明了，若 A 戴黑帽，B 可能戴黑帽、也可能戴白帽；而接下來的兩列則說明，若 A 戴著白帽，則 B 必然戴著黑帽）。不過，由於 B 回答他不知道自己的帽色，因此，我們可以把 A 戴白帽，B 戴黑帽的狀況刪除（參考圖 (4)）。

最後，問 A 知不知道自己戴哪種顏色的帽子。因為在圖 (4) 的所有可能狀況中，A 都必然戴有黑帽，所以 A 可以很有自信地回答：「我戴黑色的帽子」。