Monthly Archives: April 2013

Games People Don’t Play 续

数月前的 blog 提到的短文 Games People Don’t Play 中,作者最后留给读者下了一个未解的问题。这周末终于有时间静下心来解一下,却发现比原来想象的更困难(本来以为用型理论可以搞定,然后发现数值差太多了),于是最后只好作弊查出处 On the Autoreducibility of Random Sequences 了。 简述题目: 15人,头顶上随机分配红色或蓝色的帽子({R,B} i.i.d. 50% 概率)。每人能看到其他人的帽子颜色,但不知道自己的帽子颜色。每人可以选择猜测自己头上帽子的颜色,也可以选择放弃。成功的条件是至少有一人猜测,并且猜测全部都是正确的。不允许任何交流,也不知道别人是选择猜测还是放弃。事先可以交流并制定策略。 最简单的策略是统一指定一人作出猜测,这样是 50% 的成功率。 更优的策略涉及概率论和信息论的一些知识要点。因为有趣所以记叙于本文。 策略要点如下: 首先,任何一人的一次猜测只有 50% 的正确率。 因为帽子是随机分配的,对于作出猜测的那个人来说,别人头上帽子的颜色和他的帽子的颜色完全没有相关性,加之不允许交流,这一情形完全等同于在他的猜测后再给他随机分配帽子。 从这点看,上面 50% 的成功率似乎已经是最好的结果了。 但是还有另一个自由度,对于一人来说,他还能选择猜测的时机。 简化起见,考虑只有3人的场景。策略是如果看到其他二人帽子颜色相同,就猜测相反颜色,否则放弃。考虑4种等概率情况,RRR,RRB,RBR,BRR (另外4种对称)。RRR 下全员猜错,而其它3种情况下都是一人猜测并猜对。这一策略下成功率上升至 3/4。 注意在4种情况下总共3人做了6次猜测,一半正确一半错误,与(1)并不矛盾。可见,好的策略的必要条件是,如果结果成功,让尽可能少的人做猜测,而如果结果失败,则让每个人都做出猜测。 在人数增加的情况下,策略将更复杂。需要使用1位纠错码的知识,用来决定究竟由谁来做出猜测,猜红还是蓝。 (查出处前,我的思路到这里,没有毅力继续找纠错码了) … Continue reading

Posted in Science | Tagged , | Leave a comment