28# dbzh

问题一：说“每个人对错各2^(2N-1)次”的依据是什么？

问题二：“2^2N种情形下”是因为你没有考虑对每个人进行编码（把2N个人从1到2N编一个码）。我现在再想编码是不是必要的？如果不对参与者进行编码，像那种保证N个人正确的策略是不是被遗漏在外了？ 说说你对这个问题的看法？

对于N=1的情况，大家可以证明是不成立的，由此可以说明N>=1时也不成立，因为它不满足N=1的情况，这是数学当中的反例，但是如果取N>1，大家又该怎么处理呢？我认为这道题涉及到概率当中的数学期望的概念，每个人带红色帽子或者蓝色帽子的概率是1/2，共有2N个人，此时的数学期望是2N*1/2=N，不会出现N+1的情况，因此不存在这样的策略。

第一个问题，每个人的结论只取决于其他人，而自己的有两种可能，当然一半队，一半错。

所给不就是编码的结果吗？

哦，对，的确已经编码了！是我想错了

那么你给出的是基于直观概率论的想法，和32楼朋友的想法是一样的。这种“证明”我在顶楼的那个连接里已经说过了，而且在那个连接里给出了定义和细节上比较完备的一个说法。但正如我在２３楼里指出的那样，我认为这不是真正的证明。

这不是基于概率的证明，而是严格的证明。所给出的一半对对一半错是精确的，运用的是抽屉原则。

我不知道你认为的真正意义上的证明是什么，可以说明一下吗？
从数学的角度来说，证明不存在的结论最好的方法是反证法，根据我在32楼的思路，再加几个反设，就可以构成这样的反证法。这样就可以从逻辑上证明不存在那样的方法。
但是如果用别的方法证明不存在，数学归纳法无疑是另一个好的方法，但要构建递推的关系，本题不能说无法构建，但是没有反证法来的快。
如果再寻求别的方法，个人感觉很难，逻辑上一般会有漏洞的。

如果每种情形都有N个以上人对，则全部情形的总和应该有N*2^(2N)个人对，由此来构造反证，难道不是严格意义上的证明吗？

这种反证法缺乏构造法所能带来的洞见性内容。可惜基于构造的证法我还想不出。

应该是数学推导

回复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)。矛盾。所以这样的策略不存在。

回复W同学：

不是反证法的问题，而是你证明的时候排除不了概率的直观意义。这个是我在我看来是含混不清的。当然很多人认为也可以接受基于概率的证明，那就算因人而异吧！不用再争论了。你问我什么才算一个真正的证明，我觉得楼上就算一个真正的纯数学和逻辑的证明。

因为非A即B,0/1概率,要保证N+1可以采用周期性策略,即以封闭性,头围相连可以保证/

题目确实有点小晕