注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

格物窮理 玄陰極地

生殺動靜 順勢擇吉

 
 
 

日志

 
 

转载:猜帽子  

2015-02-15 15:25:09|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
猜帽子问题合集(一)上课的第九天,Mr. Holmes让我们每个人戴一顶帽子去上课,于是我很快就猜到——我们肯定要讨论猜帽子的问题了~猜帽子的问题我很早以前就听说过,不过还从来没有认真思考过,所以这些题目也可以算是我第一次见吧~

 

首先,Mr. Holmes让我们同桌之间玩一个游戏:总共有两种颜色的帽子——红色和蓝色,两个人随机戴上一顶,每个人只能看到对方头上的帽子颜色,要猜到自己头上的帽子颜色,然后在数完3、2、1之后,大声说出来,或者选择沉默。胜负判定是这样:如果两个人都沉默,两个人都输;如果只有一个人说,对了两个人都赢,错了两个人都输;如果两个人都说,那么只要有一个人对,两个人都算赢。

 

我那天的同桌是Krystyna,我跟她稍稍讨论了一会儿便找到了一个必胜策略:

 

A说B帽子的颜色,B说A帽子相反的颜色。

 

为什么这就是必胜策略呢?很容易证明:总共有两种情况,当两个人帽子颜色一样的时候,A就会说对;当两个人帽子颜色不一样的时候,B就会说对。虽然这样每次总有一个人错一个人对,但是按照规则,只要有一个人说对就赢了。

 

当然,这个简单的问题只能算是热身,接下来Mr. Holmes让我们三人一组讨论下一个问题:仍然只有两种颜色的帽子,红和蓝,三个人都随机戴上一顶,只能看到其他人帽子的颜色,同样是要在数完3、2、1之后大声说出自己帽子的颜色,或者选择沉默。不过这次的胜负判定有所不同:全都沉默那么都输;说的人当中只要有一个人说错,那么还是都输。也就是说,不管有几个人说,每个说的人都必须说对才能都赢。

 

我们三人讨论了一会儿,没有发现什么必胜策略(后来Josh用expected value证明了确实没有必胜策略),但是有最佳策略:如果一个人看到其他两个人的帽子颜色不同,那么他保持沉默;如果看到其他两个人的帽子颜色相同,那么他就说相反的颜色。

 

让我们来算一下这个策略的获胜概率:

总共有两种情况,三个人帽子颜色相同(红红红、蓝蓝蓝)的时候,我们全都会说错,所以会输;三个人帽子颜色不同(红红蓝、红蓝红、红蓝蓝、蓝红红、蓝红蓝、蓝蓝红)的时候,只会有一个人说,而且会说对,所以大家都会赢,所以获胜概率是2/8=75%。

 

接下来Mr. Holmes问了我们一个问题:每个人猜中自己帽子的颜色的概率都应该是50%,为什么最后的获胜概率会是75%呢?

 

为了回答这个问题,我们不妨列一个表格。为了方便起见,我们用0代表红色,1代表蓝色,P(Pass)代表保持沉默。

情况     结果

000      111

001      PP1

010      P1P

011      0PP

100      1PP

101      P0P

110      PP0

111      000

 

我们纵向地看结果列,会发现:针对每个人来说,总共有4次猜测,2次猜中、2次猜错。这符合50%的概率。然而输的情况是所有人一起错,赢的情况是只有一个人说且说对。

这就是为什么获胜概率会大于每个人的猜中概率——大家要错都错在一起,要对只有一个人对而其他人沉默。

 

下一个猜帽子问题就不是那么简单了:仍然是红蓝两种帽子,这次8个人排成一列,排在后面的人可以看到前面的人的帽子颜色,也就是说最后一个人可以看到前7个人的帽子颜色,而第一个人谁也看不到。从最后一个人开始,每个人必须猜自己的帽子颜色(注意是必须猜,不能选择沉默;每个人的猜测其他人都能听到),只有在所有人都猜中的情况下,大家才能赢;只要有一个人猜错,那么大家都输。

 

如果没有策略,只是随机猜测的话,那么获胜的概率将是1/256。

 

很快我们想到,既然后面的人可以看到前面的人帽子颜色,我们可不可以让后面的人以某种方式把信息传递给前面的人呢?当然,除了猜自己颜色以外,其它什么话都不能说的。

所以,我们想到了一个方法——偶数位的人就说出前面一个人帽子的颜色,然后前面的人就可以知道自己帽子是什么颜色的了。

这样我们可以保证所有奇数位上的人都能猜对,而偶数位上每个人都有1/2的可能性猜对,所以获胜概率是1/16。这个概率已经大大高于随机猜测的概率了,不过Mr. Holmes说,还有更好的方法。

 

我想,这个方法是后面一个人把信息传递给前面的一个人,那么有没有可能后面一个人同时把信息传递给前面两个人呢?于是,我想到了一个更好的方法:

8号(最后一个人)观察6、7号的帽子颜色,如果相同就说“红”,不同就说“蓝”;轮到7号猜的时候,他能看到6号帽子的颜色,也可以通过8号的回答知道自己帽子颜色与6号相同还是不同,所以7号就可以正确说出自己帽子的颜色;这个时候6号既能正确知道7号帽子的颜色,也能从8号的回答中知道自己帽子颜色与7号相同还是不同,所以6号也能正确说出自己帽子的颜色!

同理,5号也可以把信息传递给3、4号,然后2号再把信息传递给1号。这样只有2、5、8号不能保证猜对,所以获胜概率是1/8,又提高了一倍!

 

然而Mr. Holmes说,这仍然不是最佳方案。难道后面的人还可能同时把信息传递给前面三个人吗?不行啊,三个人的帽子颜色排列情况就太多了……

 

不对!可以的!(这是我在写这篇文章的时候新想到的方法!天哪!)

 

8号先观察5、6、7号帽子的颜色,如果有两个红色或者没有红色,就说“红”,如果有两个蓝色或者没有蓝色,就说“蓝”。比如是说“红”的情况,这样7号再观察5、6号帽子的颜色,如果发现都是红色,那么自己就是蓝;如果发现有一个红色,那么自己就是红,如果发现都是蓝色,那么自己也是蓝色!

同理,6号看得到5号的颜色,也知道7号的颜色,再根据8号的回答就可以推测出自己帽子的颜色。5号也可以根据6、7号的帽子颜色以及8号的回答推测出自己帽子的颜色。

然后4号再用同样的方法同时把信息传递给1、2、3号。

于是,用这种策略只有8号和4号无法保证猜对,获胜概率是1/4!

 

然而这还不是最佳策略!(尽管我为我想到这个方法非常高兴~)

 

也就是说,我们可以保证前7个人都能猜对!那么最后一个人必须要把信息同时传递给前7个人!

这个方法我没想到,是同学想到的:

8号观察前面所有人的帽子颜色,如果红色出现偶数次,那么就说“红”,如果红色出现奇数次,就说“蓝”。

假如8号说的是“红”,那么前面所有的人都知道,1~7号中红色出现偶数次。然后7号观察前面所有人帽子的颜色,如果有偶数顶红帽子,就说明自己是蓝色;如果有奇数顶红帽子,就说明自己是红色;然后6号观察前面所有人帽子的颜色,同时他也知道7号帽子正确的颜色,如果在1~5和7号中有偶数顶红帽子,就说明自己是蓝色,如果有奇数顶红帽子,就说明自己是蓝色。

以此类推,除8号以外,所有人都可以正确知道自己帽子的颜色!

所以获胜概率是1/2!这就是最佳策略!

 

(写到这里,我猛然醒悟:我之前想到的获胜概率是1/4的策略跟这个不是一样的思路嘛!如果我当时在课上就想到1/4的策略,这个最佳策略我说不定也就想出来了!)

 

接下来的猜帽子问题是boss级的(当然,猜帽子问题有很多很多很难的题目,不过这个问题在Mr. Holmes给我们出的题目中是最难的了,我们想了整整3天!):

这有点像之前说的3个人猜帽子问题,不过是7个人。也就是说有两种颜色的帽子,红和蓝,7个人都随机戴上一顶,只能看到其他人帽子的颜色,同样是要在数完3、2、1之后大声说出自己帽子的颜色,或者选择沉默。如果全都沉默,那么都输;说的人当中只要有一个人说错,那么还是都输;每个说的人都必须说对才能都赢。

 

在这篇文章中我就先不把答案写出来了,大家先自己想想吧~这真的是道很有意思也很有挑战性的题目。我之后会把关于这题的一系列讨论写在另一篇文章里。

 

待续。

猜帽子问题合集(二)上一篇文章的最后,我说到了一个boss级的猜帽子问题:有两种颜色的帽子,红和蓝,7个人都随机戴上一顶,只能看到其他人帽子的颜色,同样是要在数完3、2、1之后大声说出自己帽子的颜色,或者选择沉默。如果全都沉默,那么都输;说的人当中只要有一个人说错,那么还是都输;每个说的人都必须说对才能都赢。

 

其实这个大概会是什么样的解法并不难猜到,因为跟3个人的情况很像:

 

大家要错都错在一起,要对只有一个人对而其他人沉默。

 

但是这只是理论上的说法,实际能做到吗?又该怎么做呢?在解决问题之前,先让我们来做一个简单的计算:

设有n个人,那么总共就会有2^n种帽子颜色分布情况;

再设有d种输掉游戏的情况,那么就有(2^n-d)种获胜情况;

由于我们想让每种获胜情况只有一个人对而其他人沉默,所以我们就有(2^n-d)次正确的猜测;由因为我们想让每次输掉游戏时所有人都错在一起,所以我们将有dn次错误的猜测;

根据概率,猜测正确和错误的可能性应该相等,所以得到(2^n-d)=dn,化为d=(2^n)/(n+1),显然d应该是正整数,所以(n+1)必须是2的幂。在这题中n=7,那么代入计算一下得到d=16,16/128=1/8!

也就是说,最佳策略只有1/8的情况会输,获胜概率将达到7/8!

 

当然计算归计算,到底我们应该用怎么样的策略呢?单凭猜测,获胜概率只有1/2,那么我们至少要先找到一个方法比1/2好一些吧?

 

让我们把可能性列出来:

红   蓝   情况

0     7       1

1     6       7

2     5      21

3     4      35

4     3      35

5     2      21

6     1       7

7     0       1

 

可以看出,帽子数量为3:4的情况最多,所以我们可以放弃所有2:5的情况而保证3:4的情况一定获胜;同样地,放弃所有0:7的情况而保证1:6的情况一定获胜。

 

策略如下:

如果看到其他人的帽子数量比是2:4,则说数量少的那一种颜色;

如果看到其他人的帽子数量比是0:6,则说没有的那一种颜色;

其他情况则保持沉默。

 

这样我们的获胜概率是(35+35+7+7)/128=21/32,超过了1/2,不过离7/8还有不小的差距。怎么才能改进这个方法呢?怎么才能保证大家要错都错在一起,要对只有一个人对而其他人沉默呢?

把问题说得更具体一些就是我们要找16种情况,保证所有人运用某个策略遇到这16种情况都会说错,而遇到其他情况有且只有一个人说对。

 

为了方便起见,我们用数字串来表示具体情况,0代表红色,1代表蓝色,比如(0100111)。

所有的可能性也就是2^n个串,策略应该是这样:

实现约定若干个串(就叫它们“保留串”吧),然后观察其他人帽子的颜色,如果都符合某一保留串,那么自己就说该保留串中自己那一位的相反的颜色;如果没有一个其他人帽子的颜色不符合任何一个保留串,那么就保持沉默。

 

我们来看看这样的结果是什么:

如果实际情况恰好就是这些保留串之一,那大家就全猜错了;如果实际情况与所有保留串都相差两个数字以上,那大家全部放弃;如果实际情况与某个保留串恰好差一个数字,那只有一个人猜对,其余人放弃,从而获得胜利。

 

可能这样的描述太过抽象,那就让我们回到3个人的情况:

在3个人的情况下,(000)和(111)就是我们事先约定好的保留串。

比如说实际情况是(101),那么第一个人看到的将是(?01),不符合任何一个保留串,所以他保持沉默;第二个人看到的是(1?1),符合保留串(111),于是他将说自己那一位上相反的颜色也就是0,于是他说对了;第三个人看到的是(10?),不符合任何一个保留串,所以他也保持沉默。

但如果实际情况是保留串之一,比如(000),那么每个人看到的串都将符合保留串(000),所以大家都会猜1,所有人同时错。

 

于是,我们现在要做的就是试图找一些保留串集合,使得所有情况中和某个保留串只差一个数字的情况尽可能的多。

 

需要注意的是,我们必须要保证,任意两个保留串之间不能只差一个数字,否则就会出现“模棱两可”的情况。举个例子,如果我们两个保留串是(0000000)和(0000001),那么假如最后一个人看到的情况是(000000?),那么他将发现这个情况符合两个保留串,就不知道该说0还是1了。

 

如果两个保留串之间差两个数字会有什么情况发生呢?比如(0000000)和(0000011),那么假如实际情况是(0000001),第六个人看到的将会是(00000?1),符合(0000011),所以他会说0,正确;第七个人看到的将会是(000000?),符合(0000000),所以他会说1,正确。尽管可以获胜,但又两个人同时正确,有点“奢侈”。

 

所以说,我们要保证任意两个串之间都至少有3个数字不同,于是我们从(0000000)开始,从小到大罗列出这些保留串……

 

等一下,两个串的大小怎么比较呢?

串的大小比较跟多位数大小比较相似,都是从左边(高位)开始比,比如(00364)>(00295)。

 

于是,我们要寻找的保留串如下:

0000000

0000111

0011001

0011110

0101010

0101101

0110011

0110100

1001011

1001100

1010010

1010101

1100001

1100110

1111000

1111111

总共16个。

 

也就是说,如果实际情况不是保留串之一,那么有且只有一个人会说并且说对,比如实际情况是(0010010),那么只有第一个人会发现其他人的帽子颜色是(?010010),符合保留串(1010010),所以他会说0,正确!而如果实际情况恰好是保留串之一,那么所有人都会同时说错。

这是Mr. Holmes在讲这道题的时候我记的……

 

好了,这个boss级的问题我们也解决了!

 

其实,我们找到的这些保留串与C3 group有关,C3 group的定义如下:

C3 is the collection of strings that each of which is the the smallest with respect to differing from each previous string in C3 in at least three positions.

 

我们的保留串相当于是二进制C3 group的一部分。

 

C3 group有很多神奇的性质。

 

举个例子,很多人都应该听说过Nim游戏,就是说有两个人和若干堆硬币,每个人每次必须从其中一堆中拿走若干硬币,但不能同时从不同的堆中取硬币,取到最后一枚硬币的人获胜。

 

在二进制C3 group中,如果从最右边开始,每一位代表一个正整数,0表示没有,1表示有,那么每一个二进制的C3串都代表一个“先取者必败”的情况!

 

比如(1010010)代表(7,5,2),也就是说有3堆硬币,分别是7、5和2枚,两个人轮流从其中一堆中取走若干枚,那么后取的人有必胜策略!

很神奇,不是吗?

 

关于C3 group的更多性质以及Nim游戏的推广,我在之后的文章中会慢慢讨论。

http://hi.baidu.com/simonkuang26/item/4e513e104e4b564fe75e06bb
http://hi.baidu.com/simonkuang26/item/e371bd232f2e2254c28d596e

  评论这张
 
阅读(249)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017