论坛风格切换切换到宽版
  • 696阅读
  • 0回复

[投票]微软面试:五个囚犯—— 难倒无数人的智力题 [复制链接]

上一主题 下一主题
离线妞妞super
 
发帖
155
C币
-286
威望
22
贡献值
33
银元
12
铜钱
639
人人网人气币
0
只看楼主 倒序阅读 使用道具 楼主  发表于: 2011-04-11
5个囚犯,分别按1-5号在装有100颗绿豆的麻袋抓绿豆,规定每人至少抓一颗,而抓得最多和最少的人将被处死,而且,他们之间不能交流,但在抓的时候,可以摸出剩下的豆子数。问他们中谁的存活机率最大?

提示:
1,他们都是非常聪明的人
2,他们的原则是先求保命,再去多杀人;不能保命的话,也要多杀人。
3,100颗不必都分完
4,若有重复的情况,则也算最大或最小,一并处死 (中间数的重复不算)。

要有解释
真的不要小看这题 超难超难的!

——————————————————————————

所有人都想保全自己性命,而且抓取的绿豆数目大小取决于第一人的抓取数量若第一人抓取数目为n时第二人为保全自己肯定抓取n+1或n-1或n,这样他才不至于让后面的人插到第二人和第一人之间从而保全自己。这里不考虑第二人抓取的数目等于第一人抓取的数目,因为这 样的话,每个人都会抓n,那么都得死(只要n不大于100的5等份平均数)。另外题目给的信息我们知道平均数是这个题目的关键


现在分析第一人:

他有以下几种不同情况:抓取数量n为整数,数目在1n等于20时;数目n大于20而小于96时(肯定要小于96了,因为要保证每个人都能拿到一颗!)。又考虑到第二人可能取n-1的情况,因而n=2
时,也做一个节点分析。因此情况共分为:n=2时;2n>20时


1、n=2时
100%死
第一人取n=2时,第二人肯定取3,而不会取1,因为1死定了。第三人得出平均数2.5时,考虑到没人取1时,他肯定也不会取2,因此肯
定取3,同理第四、第五人都会取3,因此第一人肯定死,所有人也都会死(这里考虑到他们不能交流,而都想保全自己性命的这个前提)。
另外,我们从这个假设中,分析得出没有人愿意取n=2


因此我们有必要分析一下n=3时的情况:

2、n=3时
结论:100%死
分析:因为大家都知道没有人会取n=1,因此也不会有人取n=2(因为在没人愿意取1的情况下n=2最小),此时第二人肯定取n=4,以此论
推,第一人还是死,所有人也都会死


3、3不管取3全自己也会取与平均数相邻的一个整数,而结果是所有人都是最大和最小的,因为没有中间值


4、n=20时,
结论:第一人有可能取n=20,因为不死的概率是一半。但考虑到第二个人为避免死,肯定会取19,依然都是死。
分析:此时第二人取19或21,若第二人取19,第三人要么取19,要么取20,第四第五人也会取19或20结论依然都是死。
若第二人取21,第三人要么取21,要么取20,第四人也一样取21或20,但最后一个人无论如何,都会小于20,此时第一人不会死,第二人和最
后一人肯定死,第三人和第四人如果不是傻子也肯定取20而不会死

5、96>n>20时
结论:第二一定能活、第三、第四人有可能活,而第一人和最后一人肯定死。
分析:若第一人取n在93>n>20时,第二第三第四人为避免自己数目最大,因此会取n-1,而不是n+1(当然在n大于50时,第二第三第四人只能取小于n的数目啦),此时第一人是死,最后一人也是死,而第二人肯定能活,第三、第四人有可能能活(因为第二人有可能就剩下3颗绿豆,不过这也太阴险了点。呵呵!)


这里面还有一个特例,就是第一人取95时,就第二人活,其它一定死,第一人取94时,第二人能活,第三人有可能活,其它一定死,当第一人

取93时,第二人能活,第三有可能活,第四人在第三人能活的前提下有可能活,其它人一定死


总的来说,这5个人里面要是有人能活,只存在两种情况,其它情况下都一定死第一种情况:第一人取20,而第二人取21,此时能活的是取20的人,也就是说第一人一定活,第三、第四人取21死,取20就活。一定死的是第二人和最后一人



第二种情况:第一人取大于20且小于93的数目时,第一人和最后一人肯定死,第三第四第五人只要取小于第一人的数目就活
这里面还有一个特例,就是第一人取95时,就第二人活,其它一定死,第一人取94时,第二人能活,第三人有可能活,其它一定死,当第一人

取93时,第二人能活,第三有可能活,第四人在第三人能活的前提下有可能活,其它人一定死。
针对题目的问题,我的结论是:
第一人若取20颗绿豆时有可能活,概率为一半(因为第二人要么取19,要么取21)。
第二人在第一人取大于20颗而小于94绿豆时一定能活,第三第四人有可能活,其中第三人的几率大于第四人。


若第一人取94时,第二人一定能活,第三有可能活,其它人一定死。
若第一人取95时,第二人一定能活,其它人一定死。
在其它任何情况下,大家一起死。(怎样?好恐怖吧)

说到概率的话,具体大小我说不上来,但活命概率的大小我认为是:第二>第三>第四>第一>第五。


5个囚犯的策略
由题设条件可知:摸到最大绿豆数的囚犯必死,摸到最小绿豆数的囚犯必死,摸到重复绿豆数的囚犯必死。
整体来看,至少有两个囚犯必死。绿豆数为5时,2个囚犯必死(11111)。绿豆数为4时,3-4个囚犯必死(1211,2111)。绿豆数为3时,4-5个囚犯必死(131,311,221,212)。绿豆数为2、1时,5个囚犯必死

5个囚犯的策略应该是:5个囚犯必须使摸到的绿豆数不重复,这样才会有最多存活机会;又必须使自己摸到的绿豆数居中,才会有最大存活机会。
明确了这一点,就可以往下分析了。

具体分析求机率

设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号囚犯存活机率最大。
x>=20,有人会那么傻吗?
2一看有人大于20,得,上面有保护伞,下面也肯定有人颠底,因为不可能都>x,于是取x-1
3同理取x-2
4 x-3
5惨了100-4*x+6 铁定最小,问题来了,x>26,豆子就不够了
5死定了总情况数:16种
1可存活情况14种 =16-2
2 14 =16-2
3 12 =16-2*2
4 8 =16-2*2*2
5 0 =16-2*2*2*2
1和2机率最高


这道题要用数学来证明似乎很头疼 但是要用逻辑学解释就非常简单

这个逻辑就是活命原则:既然说了囚犯先是保命 在保不了命的情况下,会选择同归于尽

同时还有个原则是:所有豆子不必抓完 这就保证了囚犯同归于尽的条件


那么分析只有一种情况 那就是当第一个人选N个 后面的人只能在N+1 N N-1里面挑 每一个人活命都必须指望后面人的安排 而前面都是已经既定无法改变的了

那么 一号无论选多少颗 他的保命是在第二个人也能保住命的前提下 第二个人是在第三个人的能保命的情况下 以此类推


按照无数种算法 总有人活下来总有人死 虽然他们互相不知道前面的人各自拿了多少颗 但是可以摸清楚剩余的有多少颗

由于不存在第一个人活了 还能第二个人活 更到第三个活的连续摸法 又由于他们很聪明都能算清楚在自己之前的人已经会有死的了,而死人一定是要同归于尽


因此,由于都不想死,死了要拉垫背的精神作怪 每一种使人活下来的办法都会受到破坏,除非他们都不聪明也不会死了要拉垫背的,然后瞎摸,可能会有些活路


所以,最后一号囚犯在推算过所有活法之后,慷慨选择抓100个,他说:反正我抓多少颗大家都是有死有活,死的不会让我活,即使是不让别人活,但别人像我一样也推算过之后,肯定还不会让我活;而我既然会死也没必要让有些人活,所以,不如让我们一起死个痛快,后面四个哥们呀就不用在纠结算了

——————————————————————————
根据题意,2号是知道1号抓了几颗豆子的。那么,对于2号来说,只有2种选择:与1号一样多,或者不一样多。我们就从这里入手。

一.假如2号选择与1号的豆子数不一样多,也就是说2号选择比1号多或者比1号少。选择一样多的情况后面再讨论。

1.1.   我们先要证明,如果2号选择比1号多或者比1号少,那么他一定会选择比1号只多1颗或者只少1颗。为什么2号不会选择多2颗或更多,也不会选择少2颗或更少呢?要证明这个并不算太难。因为每个囚犯的第一选择是先求保命,要保命就要尽量使自己的豆子数既不是最多也不是最少。当2号决定选择比1号多的时候,那么,他已经可以保证自己不是最少,为了尽量使自己不是最多,当然比1号多出来的数量越小越好,因为这个数量越大,那自己成为最多的可能性也就越大。反之,当2号决定选择比1号少的时候,也是同样的道理,他会选择只比1号少1颗。这个证明并不难,相信大家都能理解。这个证明也很重要,以后的许多推论,都是基于这个证明。

1.2.   好了,既然2号只会会选择比1号多1颗或者比1号少1颗,那么1、2号的豆子数一定是2个连续的自然数,和一定是2n+1,其中1个人是n,另1人是n+1。轮到3号的时候,他可以从剩下的豆子数知道1、2号的数量和,也就不难计算出n的值。而3号也只有2个选择:n颗或者n+1颗。为什么3号不会选择n-1或者n+2呢?这完全是基于同1.1.的证明中一样的道理,这里不再赘述。

    不过,3号选择的时候会有一个特殊情况,在这一情况下,他一定会选择较小的n,而不是较大的n+1。这一特殊情况就是,当3号知道自己选择了n后(已保证自己不是最多),剩下的豆子数由于数量有限,4、5号中一定有人比n要少,这样自己一定可以活下来。不难算出,这个特殊情况的n=20或者n>20。也就是说,当1、2号选择了20和21颗的时候,3号只要选择20颗,就可以保证自己活下来,因为剩下的豆子只有39颗,4、5号至少有一人少于20颗(这个人当然是后选的5号),这样死的将是5号和1、2号中选21颗的那个人。
也由此我们可以看出,1号、2号都不会选择21这一“倒霉”的数字(因为他们都是聪明人),1号的选择肯定在20颗以下,而当1号选了20颗时,2号就不会再选择比1号多1颗,而只会选比1号少1颗的19。也就是说,上述“特殊情况”只是理论上的存在,实际不会发生。

1.3.   如上面所述,前2个人的和是2n+1,第3个人也只能选择n或者n+1,那么前3个人的数量和只能是3n+1或3n+2这两种可能。第4个人也是不难从剩下的豆子数知道1、2、3号的数量总和的,也就不难进而计算出n的值。同样,他也有n或者n+1这两种选择。

1.4.   与1.3.相同的计算方法,前4个人的总和,也只有4n+1,4n+2,4n+3这三种可能。最后的5号也是不难算出n的。在前4个人只选择了2个数字(n和n+1)的情况下,5号已是必死无疑,这时,根据“死也要拉几个垫背”的条件,5号会选择n或n+1,选择5个人一起完蛋

二.好了,根据第一点中的推论,如果2号选择了与1号不一样多的话,最终结果是5个人一起死,那么2号只有选择与1号一样多了。那么1、2号的和就是2n,而3号如果选择n+1或者n-1的话,就又回到第一点的情况去了(前3个人的和是3m+1或3m+2),于是3号也只能选择n。同样,4号还是只能选n,——最后的结果仍旧是5个人一起完蛋!

因此,此题的答案是:不存在“谁活下来的可能性比较大”的问题。实际情况是:5个人都要死
评价一下你浏览此帖子的感受

精彩

感动

搞笑

开心

愤怒

无聊

灌水
快速回复
限100 字节
如果您提交过一次失败了,可以用”恢复数据”来恢复帖子内容
 
上一个 下一个