帽子的机制设计和证明

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

很早以前看到的一个题目。

2N（N>=1）个人玩一个游戏：

在每个人头上都戴上一顶或蓝或红的帽子，每个人都能看见别人的帽子的颜色，但看不见自己帽子的颜色。游戏时禁止以任何方式传递信息。但游戏开始前，所有人可以在一起商定一种策略。游戏开始后，便要求所有人同时说出自己帽子的颜色。证明，无论如何不存在一种策略，保证在任何情况下都有至少N+1个人猜对。

（这个题目原先是要你找出一种策略，保证任何情况下都有N个人猜对。我现在在想，如何证明不存在保证任何情况下N+1个人猜对的策略呢？我在http://tieba.baidu.com/f?kz=597670042这个帖子的13楼说了一个基于概率论的“证明”。但我始终觉得这个说明不是很清楚，没有严格的说服力。希望大家能说说自己的看法和思路，一定会对我有所帮助的！谢谢~）

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏18 回帖

关键词：机制设计 baidu 很早以前 HTTP 不存在 如何 信息 游戏

You need to think about what will be happened when n=1. There are two people. Is there any strategy which is guarantee two of them are always correct. If it is not, then you can not find it either when n>1. The key word is always. There is no if (sepical case). Therefore, the only stratey you can guarantee the half  population will be correct is Person A says what the color Person B wears, and Person B repeats what Person A says. (Person A can mean group A when n>1). Therefore, it is always half (N). (List all strategies when n=1, you will see). If it is impossible when n=1, why bother n>1.

呵呵，这个题目，和博弈论关系不大吧，应该更多的是数学推导。

证明，无论如何不存在一种策略，保证在任何情况下都有至少N+1个人猜对。

这句话逻辑上有点含糊：

如果是希望证明，找不到一种策略，保证“任何情况下成立”，那只需要找出一个情况来分析。

只需要发现这种情况下“不可能找到该策略”，其他情况必然也就不需要考察了。

您百度里面已经说了，N=1时，就不成立。

也许，您的意思是：任何比例条件下，皆不存在某种策略，确保多数人可以猜对自己帽子的颜色？

至于“找出一种策略，保证任何情况下都有N个人猜对”，我对此也有点不明白。

分析（谈不上证明）过程：

首先考察N=1：既然不限制帽子的颜色，就有三种情况：两个红，两个蓝，一红一蓝。

需要有一个策略，确保每次实验，至少有一个人说对。

我想不出这个策略。

个人感觉，这个问题之所以迷惑人，是因为混淆了“猜对颜色比例”和“猜对自己颜色的比例”这个概念。

假如提问的是，能否有超过一半的实验者，猜对总体帽子的颜色比例，即，哪种颜色更多？

那么，实验者是可以通过某种实现安排好的策略，与观察到的信息，来达到目的的。

但是否能猜对头上的帽子颜色，和观察到的信息完全没有关系。

举例而言：

你面前一定有奇数的帽子，自然有某种帽子的数量比较多，如果设定，所有人说自己的帽子颜色为看到较多的那种帽子，那会造成什么结果呢？能保证达到最少N个人说对自己帽子的颜色吗？

除非，N>=2。

Are you stupid or what? Here is the strategy: 甲说出乙的帽子的颜色，乙重复甲说的颜色。It does not matter what 乙的帽子的颜色是什么，乙is always right.

Then think 甲and 乙are two group when n>1.

楼上的，注意“同时说出”这个条件。

还有，stupid这个词强度太大，不如用foolish或者silly。

7# defeniks

but the crux is, they need to report their answers SIMULTANEOUSLY