Re: [討論] 似乎很難的問題
※ 引述《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)
推
12/27 23:13, , 1F
12/27 23:13, 1F
推
12/28 21:49, , 2F
12/28 21:49, 2F
→
12/29 14:41, , 3F
12/29 14:41, 3F
討論串 (同標題文章)