益智問答（１０）猜帽子 - 拼圖

※ 引述《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) 人以前(包含)，必定有人會知道自己帽子的顏色
而且此數無法改進



--