帽子的机制设计和证明

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)个人对，由此来构造反证，难道不是严格意义上的证明吗？

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

应该是数学推导