※ 引述《phz100 (Septem)》之銘言： : 這個問題我也不知道有解嗎 : 題目: : 現在有n個人,每個人頭上都有一頂帶某種顏色的帽子 : 帽子的顏色總共有n種,但顏色有可能會重覆 : 每個人都可以看到其他n-1個人頭上帽子的顏色,但不能跟其他人說 先做一組編碼： 每個人被編碼成 0,1,2...n-1 每種帽子的顏色也被編成 0,1,2...n-1 每個人都知道這套編碼(透過一開始的討論) 並且牢牢記熟 : 不過他們可以事先討論每個人要怎麼猜自己帽子的顏色 : 請找出一種猜法可以保證一定會有一個人猜中自己帽子的顏色 : 大家討論看看吧,很期待看到解法 那麼就可以開始了 首先每個人會看到自己以外的n-1頂帽子 將這n-1頂帽子的編碼做總和之後，取n的模數，得到一個介於0到n-1的數字a 然後 每個人要猜測的帽色就是 {(自己的編碼) -(a) +(n)} 取n的模數 這樣必然恰有一人猜中 證明： 定義1 在任何編排好的情況下，帽子編碼總和為定值。令之為S。 定理1 S取模數必定介於0到n-1之間 引理1 S取模數之結果必定等於某一人之編號，令此人編號為P。 每個人經過觀察之後，可以發現其他人的帽色，並可據此得出a。 a代表的即是 (S - 自己帽色)， 而這個數字取模數的結果和(P - 自己帽色)取模數結果相同。 因此可列式： (P - a) mod n = 自己帽色 ※計算中為P-a+n乃為了避免負數結果，但定義上即使省略亦不失正確性。 原PO可以自己設想n = 2的情況(樣本為四，而每人的猜測為對方帽子的函數) (廣義而言，可說每人會觀察到的可能情況為(n)^(n-1)種， 該人的猜測為這些案例的函數) 如有誤請指正 謝謝 --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.114.71.184 ※ 編輯: KAOKAOKAO 來自: 140.114.71.184 (12/26 14:16)