我也来个数学题，猜帽子（2012-8-7 18:00更新额外挑战部分）

AlbertNi

有100个人，每人头上戴的不是白帽子就是红帽子。这些人排成一列，每个人都能且仅能看到在他之前所有的人头上帽子的颜色（最后一个人可以看到99顶帽子的颜色，第一个人什么都看不到）。
现在，从最后一个人（能看到99顶帽子的那人）开始向前，所有人依次报出自己头上帽子的颜色。请问在运气最差的情况下，你能采取怎样的策略让尽量多的人正确报出自己头上帽子的颜色？
举例：
1、鸵鸟策略：所有人闭着眼睛瞎报，可以保证0人正确
2、互助策略：2人一组（最后一个和倒数第二个人一组，倒数第三个和倒数第四个一组，以此类推），同组的后一个人报出前一个人头上帽子的颜色，他前面的人照着报。这样有50个人一定是正确的，因为在他后面的人告诉了他自己帽子的颜色。
3、不可能策略：不可能保证100个人全部正确，因为这100个人没有人知道最后一个人头上帽子的颜色，而在运气最差的情况下，这个人总是会猜错的……

主帖会随时公布非最优策略中最好的一种（以及提出者）作为大家努力超越的目标（最优策略不会那么早公布的哟～）。

得出最优策略者也会在主帖提名表扬，小红花什么的也可以啦XD

目前最好的非最优策略：可确保83人答对
提出者：nhofb（10楼）
六人一组策略：六人一组，第一个人根据以下情况来报：（两种颜色用比例来表示）
3:2，第一人报较多的，第二人看后的情况，只有3:1和2:2，如果是3:1则报少的，如果是2:2则报第一人的色，以后的人因为知道除了自己外的其他4人的颜色，也可以适用第二人的情况。
5:0，第一人报较多的，因为每个人可以得知另外四人的颜色，而且4:1的情况是报较多的颜色，所以可以推断是同色，只要跟着第一人来报就行了。
4:1，第一人报较多的相反色，对于每个人来说只有3:1和4:0的情况，3:1的直接报第一人的相反色，4:0的因为同色的不是报相反色，所以必然是4:1，所以直接报第一人的颜色即可。

因为6人一组还剩4人，采取四人一组的方法可以解决。
可达到83人通过

目前得出最优策略者：
ooxx（9楼）
nhofb（16楼）

额外挑战（请知道最优策略者参与）
在不故意报错的情况下（比如采用6人一组策略，但是剩下4人自暴自弃全部瞎猜而且猜错，导致只有80人正确），非最优解答可以达到的人数上限是多少呢？
最好的策略将在前面的公示贴出，欢迎知道最优解者继续挑战极限！楼主本人也会参加的～

更新：楼主我突然大彻大悟了，已经领悟了这个额外挑战的真谛，现在已经可以从nhofb在10楼的答案中推导出几乎任意的更优乃至于最优解答了！感谢nhofb在10楼的启发 。于是继续提供挑战给同样“悟透”了这道题的同学：如果帽子有3种颜色，那么可以肯定最优解是不变的，非最优解是否也能像两色的情况那样进行推导乃至于能不断扩展直至最优解答呢？

“作弊”策略（兼规则讲解）：
注意“作弊”的方案只是本方案无效，参与者不出局哦！
额外信息的问题
提出者：nhofb
策略：最后一个人瞎报，如果前一个人和自己报的颜色相同则报“白色”或者“红色”，不同色则报“白”或“红”，可达到50%几率全对，50% 几率99人对
讲解：这是作弊行为哦，报颜色的时候不能掺杂其他信息，或者说在制定策略的时候不能考虑颜色以外的其他信息
注意：作为策略的一部分可以约定一些特殊的意思，比如最后两个人报的颜色不同表示最前面的人戴白帽子，相同则是红帽子。但是不允许通过语言上的花招来传递额外信息

“物理”作弊的请况
提出者：AlbertNi
策略：大家把帽子拿下来看看就好了嘛，或者用镜子啊什么的～
讲解：我是来卖萌的，大家无视就好……总之，有奇怪的想法也可以提出来！全～部～欢迎！涉及到空间扭曲，时间旅行，量子效应什么的请自重就好……恕不一一列举……

TLX099

傻瓜策略
所有统一报出自己头上帽子颜色为白色或者红色，则可以保证报出的帽子颜色相同数量的正确率。



所以比较拼运气了，最好的情况下是全部猜对。。。但这可能性太低了，除非真的敢全部同一色帽子。

nhofb

好吧，当我么说过………………

TLX099

感觉这个不太好算啊，如果按照数学来算的话，无非就是算出来每个人的头上是1或者是2.

我想的话，基本上没可能一定保证50人以上的正确率吧，毕竟这个没有任何规律可以拿来计算。

想要确切超过50人，那不能让红白帽子平衡吧？要是更是50个的话怎么来弄？

你这样不行吧？这个我想过了，可是后来又推翻了，因为前面两个人根本不知道自己头上是啥帽子，单凭后面的那个根本分不出来啊。

好吧，我又想的少了。。。

AlbertNi

规则解释有更新：作为策略的一部分可以约定一些特殊的意思，比如最后两个人报的颜色不同表示最前面的人戴白帽子，相同则是红帽子。但是不允许通过语言上的花招（比如“白”和“白色”的区别）来传递额外信息

liang

每个人都报他看到数量最多的另一种颜色，如果看到两种颜色一样就报前面报的另一种，这样可以保证最少50人答对（就是50，因为运气差，同颜色一定在一边）
改一下上面的话：51-100名跟着51报同一种~~~~~~~~~~~~好像一样（这时就是颜色相间了）
如果可以记数目的话，看到一样的颜色就报前面报的少得那种，这样就不可能出错
PS:应该没算错，有错欢迎提出
算错了！！！！！！以为颜色各50 有空再改



我再过来时已经有最优策略了  求答案

ooxx

每三人一组，从100人列排在最后面的那个人开始分组，可分33组。100人列排在最前面的那个人不属于任何组，他可以随便报颜色。

因为只有两种颜色，所以三人组成的小组中，至少会有两个人颜色一样（当然也可能出现三人颜色都一样的情况，不过这里不需要考虑这种情况）。

策略：每组中第一个报帽子颜色的人，由于他可以看到本小组中另外两人的帽子颜色，于是，以报“红色”表示小组中其他两人帽子颜色不一样，以报“白色”表示其他两个人帽子颜色一样。这样在这一小组中，第二个报颜色的人，可以根据第一个人所报的颜色，以及他所能看到的第三个人帽子的颜色来进行推论，得出自己帽子的颜色，并且报出自己帽子的颜色；而小组中第三个报颜色的人，也可以根据第一个人所报的颜色，和第二个人所报的颜色进行推论得到自己帽子的颜色，并报出自己帽子的颜色。

结果：在这33组中，每组以牺牲第一个报颜色的人的方式，确保另外两人所报颜色绝对正确，这样在这100人列中，至少会有66人报出正确的颜色；而且裁判只接收颜色信息，所以每组的一个人所报的颜色，也会有50%的概率与自己帽子的颜色相同，也就是说，除了66个可以正确报出自己帽子颜色的人之外，其他34个人，每个人也会有50%的概率报出正确的颜色。

（举例：每组中第二个人，他可以看到第三个人帽子的颜色，如果第一个人报了红色，那就说明第三个人帽子的颜色与自己的不同，于是报出相反的颜色即可；反之如果第一个人报了白色，那么就说明第三个人帽子的颜色与自己是相同的。每组中的第三个人，如果第一个人报了红色，那么他报出和第二人相反的颜色即可；如果第一个人报了白色，那么他报出和第二个人相同的颜色即可。）

ooxx

7楼太笨了，不过可以延伸7楼ooxx提出的办法。

新方法：100人列，每4人一组，共25组。以每组牺牲第一人的方式，确保每组至少有三人报对自己帽子的颜色。这样100人中最少会有75人报出正确的颜色。

具体的，每组第一个报颜色的人，由于他可以看到另外三人帽子的颜色，（因为只有两种颜色，所以三人中必然至少有两人颜色一样）于是：如果本组另外三人颜色不全相同，则报出占多数的颜色（下称多数色）；如果本组另外三人颜色全部相同，则报出与其三人相反的颜色（下称相反色）。

每组第二个人，由于他可以看到本组剩下两人的颜色，所以他可以做如下推论：如果另外两人颜色相同，并且与第一人所报颜色相同，那么自己的帽子一定是与另外两人相反的颜色；如果另外两人颜色相同，并且与第一人所报颜色不同，那么自己帽子的颜色一定是与另外两人相同的颜色；如果另外两人颜色不同，那么自己帽子的颜色一定是第一人所报之颜色。

每组第三个人，由于他可以知道本组第二个人和第四个人的颜色，所以他可以做如下推论：如果第一人报出的是多数色（注1），并且第二人和第四人颜色相同，那么自己的帽子一定是与第二人和第四人相反的颜色；如果第一人报出的是多数色（注1），并且第二人和第四人颜色不同，那么自己的帽子一定是第一人所报之颜色；而如果第一人报出的是相反色（注2），则自己的帽子一定与第二人和第四人都是一样的颜色。

每组第四人，同样由于他可以知道本组另外两人（第二人和第三人）的颜色，所以他可以做如下推论：如果第一人报出的是多数色（注1），并且第二人和第三人颜色相同，那么自己的帽子一定是与第二人和第三人相反的颜色；如果第一人报出的是多数色（注1），并且第二人和第三人颜色不同，那么自己的帽子一定是第一人所报之颜色；而如果第一人报出的是相反色（注2），则自己的帽子一定与第二人和第三人都是一样的颜色。

注1和注2：由于每组后三人都可以知道除第一人外另外两个人帽子的颜色，所以，当另外两人帽子颜色不同，或者另外两人帽子颜色相同并且与第一人所报颜色相同时，第一人报的就是多数色；相反滴，如果另外两人颜色相同但却与第一人所报之颜色不同时，第一人报的就是相反色。

ooxx

当我得知75个人也不是最优结果时我几乎抓狂了…… 不过这样也好，可以知道自己究竟有多笨了。

其实呢，我们只需要牺牲第一个人，而保证其他99人答对自己帽子的颜色。

具体的，哎比我前面两楼说的都要简单。首先我们设定布尔值：红色帽子为假，白色帽子为真（用0和1来表示也可以哦）。

第一个人，把其他99人帽子的颜色逐个进行异或运算，然后报出结果，如同前面的设定，结果为假就报红色，结果为真就报白色。

第二个人呢，再把他所看到的98个人的帽子进行异或运算，所得结果再跟第一个人所得的结果进行异或运算，其结果就是自己帽子的颜色。

第三个人也是一样，只不过他需要把他所看到的97个人的帽子，和第一个人的结果，以及第二个人的帽子都进行异或运算，最后的结果就是自己帽子的颜色。

也就是说，每个人都要做99次异或运算，除了第一个人无法知道自己的帽子颜色之外，其他人都可以根据这99次异或运算的结果答对自己帽子的颜色。

nhofb

六人一组，第一个人根据以下情况来报：（两种颜色用比例来表示）
3:2，第一人报较多的，第二人看后的情况，只有3:1和2:2，如果是3:1则报少的，如果是2:2则报第一人的色，以后的人因为知道除了自己外的其他4人的颜色，也可以适用第二人的情况。
5:0，第一人报较多的，因为每个人可以得知另外四人的颜色，而且4:1的情况是报较多的颜色，所以可以推断是同色，只要跟着第一人来报就行了。
4:1，第一人报较多的相反色，对于每个人来说只有3:1和4:0的情况，3:1的直接报第一人的相反色，4:0的因为同色的不是报相反色，所以必然是4:1，所以直接报第一人的颜色即可。

因为6人一组还剩4人，采取四人一组的方法可以解决。
可达到83人通过………………