※ 引述《pikacha (小億)》之銘言： : 話說某個有＄的人想找位管家，他出了這個問題： : 這有１０個人站成一直線，每人頭上有一頂帽子，每個人都看不見自己的帽子顏色．．． : 但是每個人都能看見站在自己前面"所有人"的帽子顏色！ : ＥＸ：第１０人可以看見前面９人的帽子顏色，第９人可以看見前面８人的帽子顏色 : 　　　以此類推．．． : 　　　已知帽子有３紅，４黑，５白。 : 　　　現在問第１０人能否１００％確定自己的帽子顏色，第１０人回答說不能！ : 　　　如果依序問第９人、第８人、第７人．．．到第２人都回答說不能．．． : 　　　你能說出第一人的帽子是什麼顏色嗎？ : （或是必然有人能回答自己帽子的顏色？！） : 　　　當然，這１０個人都是厲害的推理高手！ : ==防雷== 如果沒計算錯是第六個人(包含)之前 一定會有人知道自己帽子顏色 方法是討論「自己看不到的帽子」 可以用整數的 partitions 來分類 比如說，第十人看不到的帽子， 可能性是 [3,0,0], [2,1,0], [1,1,1] 若是猜得出來， 他看不到的帽子就一定是 [3,0,0] 這種樣式 接著一步步推下去， 第九人看不到的帽子有 [4, 0, 0], [3, 1, 0], [2, 2, 0], [2, 1, 1] 這些可能性 舉例來說， [3,1,0] 會讓第九人知道自己帽子的顏色 因為在這個情況下， 第十人的可能性是 [3,0,0] 和 [2,1,0] 但若是 [3,0,0]，第十人就不會說自己不知道 另外 [4,0,0] 則是不可能出現的， 因為在這個情況下，第十人必定是 [3,0,0]， 不可能輪到第九人 接著我是寫了一個程式去列啦 手算也不是不行，但我的計算能力... 第十人: [3, 0, 0], [2, 1, 0], [1, 1, 1] 第九人: [4, 0, 0], [3, 1, 0], [2, 2, 0], [2, 1, 1] 第八人: [5, 0, 0], [4, 1, 0], [3, 2, 0], [3, 1, 1], [2, 2, 1] 第七人: [5, 1, 0], [4, 2, 0], [4, 1, 1], [3, 3, 0], [3, 2, 1], [2, 2, 2] 第六人: [5, 2, 0], [5, 1, 1], [4, 3, 0], [4, 2, 1], [3, 3, 1], [3, 2, 2] 這些代表這些人「看不到的帽子」的可能情況 黃色是可以猜出來，紅色則是完全不可能發生 可以看出第六人必定能猜出來 另外也可以知道， 如果第十人猜不出來 他所看到的帽子必定要有 白白白黑黑紅 這六頂 一旦有個人發現少了一頂 那他就一定可以知道自己頭上帽子的顏色 因此第六人之前一定會有人猜出來 但接下來要怎麼證這個六是最小的 我就不曉得了 想到了！ 就說比 [2,2,2] 「小」的 partitions 會讓人猜不出來就好了 補上最後結論: 若有 A_i 頂顏色為 i 的帽子, i=1,2,...,n，並讓 (ΣA_i)-R 個人戴上 然後玩題述的遊戲 那麼在第 Σmax(A_i-R,0) 人以前(包含)，必定有人會知道自己帽子的顏色 而且此數無法改進 --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.230.45 ※ 文章網址: https://webptt.com/m.aspx?n=bbs/puzzle/M.1460815182.A.8C3.html ※ 編輯: arthurduh1 (140.112.230.45), 04/16/2016 22:26:24 ※ 編輯: arthurduh1 (140.112.230.45), 04/16/2016 23:04:20