最后的人开始说,前一前二颜色一致说白,否则说黑。 |
最后一人开始说,说前面人的帽子的颜色 |
有十五个囚犯,每个囚犯随机的戴上了一顶黑帽子或白帽子,黑白概率各为1/2,而且十五顶帽子的颜色是互相独立的。这十五个囚徒都知道别人帽子的颜色,不知道自己的。 现在每个囚犯都要猜自己帽子的颜色。如果有多于一半的人猜对,就释放他们,否则统统杀头。 他们可以事先商量一个策略,戴上帽子之后就不能再交流信息。 是否存在一个策略,使得他们被释放的概率超过90%? 答案: 把15个人从1到15编号。 1号猜白色,不管1号猜得对不对,2到15号都能通过看1号的帽子知道1号是否猜对。 1号有1/2的概率猜对。 如果1号猜对了,2和3,4和5, 6和7, 8和9, 10和11, 12和13, 14和15, 配成7对, 单号看见对方是白就猜黑,看见对方是黑就猜白,双号看见对方是白就猜白,看见对方是黑就猜黑. 这样每对中总有1人会猜对,另1人会猜错。这样就有8人猜对。 如果1号猜错了,2和3配成1对, 双号看见对方是白就猜白,看见对方是黑就猜黑。 这样2和3 有1/2的概率都猜对,1/2的概率都猜错。并且4到15号都知道1,2,3是否猜对。 如果2,3号猜对了, 4到15号按1号猜对后的方法猜,会有8人猜对。 如果1,2,3号都猜错了, 4到7号组成一组。都猜他们4人共有双数个黑帽子。这样4人有1/2的概率都猜对,1/2的概率都猜错。 如果4到7号猜对了,8到15号安1号猜对后的方法猜,会有8人猜对。 如果1到7号猜错了,8到15号组成一组。都猜他们8人共有双数个黑帽子。这样8人有1/2的概率都猜对,1/2的概率都猜错。 总之,8人猜对7人猜错的概率是15/16, 15人全猜错的概率是1/16。 |
is more difficult. |
For the wxc's problem in my post, they can form 5 groups of 3 people each. In each group, the first person says black if the other two people have the same color, otherwise he says white. Then, the rest two people use the clue to figure out their own' color. They start from group 1, group 2, up to group 5. At least 10 people will get the color right. Am I missing something? |
还是不明白。 假设: n=黑 n-1=白 n-2=白 n=3=? . . . n看见n-1和n-2一样,所以说白。当然他错了。 轮到n-1说,他知道自己和n-2一样(因为n说白),并且他看到n-2是白帽子,所以n-1说白。他对了。 轮到n-2说,他知道自己和n-2一样(因为n说白),并且n-1说白,所以n-2也说白。他对了。 轮到n-3说,他完全没有信息,只能猜。 |
Here: |
No, it is not about the details of the solution. Both problems are actually about ideas of "coding". The problem here is indeed a parity check, the most basic coding method. The WXC problem is more complex in the sense it utilizes a far more sophisticated coding method. |
This one has condition "每个囚犯不知道别人猜了什么". Since they cannot use other people's answer, it is harder to get it right. My copy from wxc did not have such condition. |
欢迎光临 珍珠湾ART (http://zzwav.com/) | Powered by Discuz! X3 |