Re: [討論] 似乎很難的問題
※ 引述《oldfood (老食物)》之銘言:
: 鬼斗大大
: 我自己假設了兩個人甲乙 兩種顏色帽子黑白的情況
: 我還是不明白有甚麼方法可以讓 甲或是乙其中一人一定會猜中自己帽子的顏色
: (顏色可以重複代表,代表可以是黑黑/黑白/白黑/白白,這幾種情況吧)
: 請指教
那就先這樣假設好了
假設甲和乙都是熱血份子
在衝動之下就下定主意了
甲:我都猜黑
乙:我都猜白
這樣的話 按每一種情況分析會是這個樣子
甲 乙 結果
實際帽子 黑 黑 甲猜中
黑 白 miss
白 黑 都猜中
白 白 乙猜中
結果還是有機會不行
那是因為甲乙兩人都沒有認真擬訂戰略
事實上
甲的猜測可以有四種:黑、白、和乙的一樣、和乙的不一樣
乙也一樣有四種
總共16種組合 你應該可以試出可以達成條件的組合
但是這樣要試到什麼時候?
所以需要下面這些較為廣義的分析
: ※ 引述《KAOKAOKAO (鬼斗)》之銘言:
: : 那麼就可以開始了
: : 首先每個人會看到自己以外的n-1頂帽子
這個case n=2
假設黑=1 白=0
甲=0 乙=1
: : 將這n-1頂帽子的編碼做總和之後,取n的模數,得到一個介於0到n-1的數字a
: : 然後
: : 每個人要猜測的帽色就是
: : {(自己的編碼) -(a) +(n)} 取n的模數
: : 這樣必然恰有一人猜中
甲 乙
黑 黑 這個時候
甲會猜 (0-1+2) mod 2 = 1 猜中
乙會猜 (1-1+2) mod 2 = 0 猜不中
黑 白 這個時候
甲會猜 (0-0+2) mod 2 = 0 猜不中
乙會猜 (1-1+2) mod 2 = 0 猜中
白 黑 這個時候
甲會猜 (0-1+2) mod 2 = 1 猜不中
乙會猜 (1-0+2) mod 2 = 1 猜中
白 白 這個時候
甲會猜 (0-0+2) mod 2 = 0 猜中
乙會猜 (1-0+2) mod 2 = 1 猜不中
: : 證明:
: : 定義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)種,
: : 該人的猜測為這些案例的函數)
: : 如有誤請指正 謝謝
你可以自己想想看 為什麼有這樣的安排
對於n種帽子分配給n個人的情況 總共有n^n的情形
也就是說 如果可以在每個n^(n-1)種情況恰有一人猜中
那麼就可以保證每種情況都恰有一人猜的中
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 122.120.36.223
推
03/13 15:31, , 1F
03/13 15:31, 1F
推
05/26 04:36, , 2F
05/26 04:36, 2F
討論串 (同標題文章)