囚犯抓绿豆问题
(2012-08-11 12:58:48)
标签:
囚犯绿豆逻辑推理面试杂谈 |
分类: 逻辑 |
5个囚犯,分别按1-5号,在装有100颗绿豆的麻袋里抓绿豆,规定每人至少抓一颗,而抓得最多和最少的人将被处死,而且,他们之间不能交流,但在抓的时候,可以摸出剩下的豆子数。问他们中谁的存活几率最大?
条件:
1.他们都是很聪明的人
2.他们的原则是先求保命,再去多杀人
3.100颗不一定都分完
4.若有重复的情况,则也算最大或最小,一并处死。
具体分析求机率,设1号囚犯摸到的绿豆数为N。
则2号囚犯摸到的绿豆数为N+1或N-1。因为2号囚犯可以通过摸剩余绿豆的方法得知1号
囚犯摸到的绿豆数,2号囚犯摸到的绿豆数为N的话就会重复是找死,如果摸到的绿豆数与N
相差大于1的话,又会使得3号囚犯有机会使摸到的绿豆数居中。
3号囚犯也会使自己摸到的绿豆数与1、2号的紧密相邻,即使自己摸到的绿豆数比1、
2号的之中最大的大1,最小的小1。因为3号囚犯可以通过摸剩余绿豆的方法得知1、2号囚犯摸到的绿豆总数,又知1、2号囚犯摸到的绿豆数相差为1,从而判断出1、2号囚犯各自摸到的绿豆数。
4、5号囚犯与3号囚犯想法基本相同。即使自己摸到的绿豆数比自己前面所有的之中最大的大1,最小的小1。
综上所述,5个囚犯摸到的绿豆数为5个连续整数。
1号囚犯存活机率。1号囚犯有两种情况必死:摸到的绿豆数最大或最小。摸到的绿豆数最大或最小,只能由后4位囚犯决定,由分析可知后4位囚犯的摸到绿豆数的位置都只有两个,即一组连续整数的两边。因此1号囚犯摸到的绿豆数为最大时的机率为(1/2)*(1 /2)*(1/2)*(1/2)=1/16,最小时的机率也为1/16,1号囚犯存活机率为1-(1/16)*2 =7/8 。2号囚犯存活机率。由对称性可知2号囚犯存活机率与1号相同,也为7/8。
3号囚犯存活机率。3号囚犯摸到的绿豆数为最大时的机率为(1/2)*(1/2)*(1/2)
=1/8,最小时的机率也为1/8,1号囚犯存活机率为1-(1/8)*2=3/4。
4号囚犯存活机率。4号囚犯摸到的绿豆数为最大时的机率为(1/2)*(1/2)=1/4,最
小时的机率也为1/4,4号囚犯存活机率为1-(1/4)*2=1/2。
5号囚犯存活机率。5号囚犯摸到的绿豆数不是最大就是最小,必死无疑。5号囚犯存活
机率为0。
本题到此告一段落。但是5个囚犯的策略似乎有点问题:5号囚犯在必死无疑的情况下,还会为前4人保驾护航吗?他会不会临死拉个垫背的?于是有了以下分析。
5号囚犯的“觉醒”(临死拉个垫背的,在必死无疑的情况下多杀人)
1-4号囚犯策略如前,则4个囚犯摸到的绿豆数为4个连续整数,而5号囚犯的“觉醒”
促使他多杀人。要多杀人,他摸到的绿豆数必须为4个连续整数的中间两个,这样有4人必
死,只有1人存活。5号囚犯必死,4号囚犯摸到的绿豆数为4个连续整数的最大或最小值,
也必死,1-3号囚犯有可能存活。
先不考虑5号囚犯。
1号囚犯存活机率。1号囚犯摸到的绿豆数为4个连续整数的最大或最小值,则必死。1
号囚犯摸到的绿豆数为最大时的机率为(1/2)*(1/2)*(1/2)=1/8,最小时的机率也为
1/8,1号囚犯存活机率为1-(1/8)*2=3/4
2号囚犯存活机率。由对称性可知2号囚犯存活机率与1号相同,也为3/4。
3号囚犯存活机率。3号囚犯摸到的绿豆数为最大时的机率为(1/2)*(1/2)=1/4,最
小时的机率也为1/4,3号囚犯存活机率为1-(1/4)*2=1/2。
考虑5号囚犯。
由于5号囚犯摸到的绿豆数必为4个连续整数的中间两个,故1-3号囚犯存活机率都将减
半。即1、2号囚犯存活机率为(3/4)*(1/2)=3/8,3号囚犯存活机率(1/2)*(1/2)=
1/4。
5号囚犯的“觉醒”等于宣判了4号囚犯的死刑,4号囚犯考虑到这一点后,随之“觉醒”。4、5号囚犯共同“觉醒”。此情况很简单,大家同赴九泉。
综合考虑后,1、2号囚犯存活机率最大。
有一种分析是这样的:
第一个和第二个的活命机会是均等的。他们的机会关键是看剩下的人如何拿。 因为后面的看不到前面人拿的颗数,只能看到剩下的颗数。所以第一个如果拿N个,第二个就会拿N+1个或N-1个,如果他不拿N+1或N-1。就会给第三个机会拿他俩中间的数,所以第二个只会拿N+1或N-1个。而第三个则会按照袋里剩下数得出前两人拿之和。他也会尽量与他俩拿的数字接近,但不同。当前两人的和为2N+1时第三人他可以拿N+2或N-1,当前两人之和为2N-1时他可以拿N-2或N+1。 而第四人也会按照前三人之和除以三以后选择拿的颗数,但此时的平均数未必会=N,他会选择新的平均数加减2颗来拿,但也必定与前三人拿之数相连。 而第五人其实是没有活命的机会的,他只是用来决定前四人中谁陪他死的。
这样就得出结论:从死亡概率的角度来算,第一个和第二个死亡的概率是这样变化的,每当抓取的人数多1个的时候他们的概率就是前一次死亡概率P*1/2,(这里稍微解释一下,比如A,B,C三个人,下面的排序是按照他们拿绿豆的个数排列的,在C没加入之前,A,B的排列只有两种AB,BA如果没任何人加入,他们俩都得死,幸运的是C现在要加入,所以必定是这样排列的CAB,ABC,CBA,BAC。从中可以看出A和B的存活概率都增加了1/2,当然C必定死,以此类推如果加入D,则C存活的概率就回是1/2)。所以第一个和第二个后面还有3个人,故死亡的概率就为1/2 * 1/2 * 1/2 = 1/8,同理第三个人死亡的概率就为1/2 * 1/2 = 1/4,那么第四个人的死亡概率就为1/2,第5个人别想了必定要死。
但是这样分析,你会发现100课绿豆这个限定条件就没有任何意义了?就是1k和1w个绿豆都一样,那聪明的囚犯会这样想么?同样100这个数字就给了第一个囚犯机会,让他有机会决定这个豆子如何分配。所以这个分析虽然没错,但是忽略了一个前提条件,那么完整的分析应该包含下面的内容。
所以这里根据100个绿豆5个人可以看出第一个人肯定会考虑这个数字100/5 = 20。同时考虑到5人选择的数字肯定连续。那么第一个人就回考虑以下3种情况:
1, 第一人如果取1个绿豆,那第一个人智商基本为0,不符合题目要求。
2, 考虑拿的绿豆个数1<N < 5时
那么第一个人如果取1<N<5那么后果是什么那?第二人肯定取N+1,而不会取N-1,因为第二个人清楚的知道不可能出现54321这种排列了,因为第一个人取得的绿豆没有超过5个,所以如果自己取N-1自然减少了自己生存的概率,这些问题1自然可以推论出2肯定取N+1,那么自然1的生存概率就减少了,1肯定不干。
3, 考虑拿的绿豆个数18<N (这里为何是18哪?因为18,19,20,21,22的和正好是100)
那同样就不可能出现12345这种排列,所以也不可能。所以第一个人取得绿豆的合理范围是5<=N<=18.