※ 引述《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)