[其它] 帽子的机制设计和证明 [推广有奖]

41楼

imp555 发表于 2009-6-25 18:50:25

回复D同学：

你是对的而且你的想法的确是严格的。我之前把你说的一半误解成概率了。

为了方便说明，引入一个为这2N个人戴帽子的人。他的工作就是为这2N个人戴2^(2N)次帽子，让他们每次都按照选定的策略进行游戏，从而穷尽所有可能的戴帽子方式！（amen! 但愿N值不要太大，不然这群人肯定要罢工了）

证明用反证法，假定存在这么一种策略保证至少N+1个人正确。

第一步，考察1号。这个2^(2N)次的戴法可以被分成两个互斥的子集S1和S2。S1={1号戴的是蓝色帽子时的所有戴法}，S2={1号戴的是红色帽子时的所有戴法}。进一步的，容易验证，#(S1)=#(S2)=2^(2N-1)。

第二步，定义F1为1号的策略函数，它把1号看见的其他2N-1个人的帽子颜色的可能组合映射到值域Z={1号戴的是红色帽子，1号戴的是蓝色帽子}. 现在注意到关键的一点，S1里的每个元素s1i，都可以找到S2里的唯一元素s2i，两者所描诉的2到2N号的颜色组合是完全一样的。那么F1（s1i里2到2N号的颜色组合）=F1（s2i里2到2N号的颜色组合）。但s1i里1号戴的是蓝帽子，而s2i里1号戴的是红帽子。所以F1（s1i里2到2N号的颜色组合）和F1（s1i里2到2N号的颜色组合）两者总有一个正确，且仅有一个正确。所以在所有的2^(2N)种戴法中，1号刚有一半的次数即2^(2N-1)次回答正确。

第三步，由于1号的选择没有特殊性，这个结论对于所有人都成立。所以定义A为在2^(2N)次游戏中所有人回答正确的次数和，那么必然有A=2N*[2^(2N-1)]. 这是一个对于所有策略都成立的量。如果真有一种策略保证每次都有至少N+1个人正确，那么A>=2^(2N)*(N+1)=2N*[2^(2N-1)]+2^(2N)。矛盾。所以这样的策略不存在。