荣耀联邦吧 关注:14贴子:533
  • 2回复贴,共1

老题:五个囚犯

只看楼主收藏回复

  5个很聪明的囚犯,分别按1-5号在装有100颗绿豆的麻袋抓绿豆。规定每人至少抓一颗,而抓得最多和最少的人将被处死,抓的豆数相同的人一并处死,而且,他们之间不能交流,但在抓的时候,可以摸出剩下的豆子数。问他们中谁的存活机率最大? 


1楼2008-02-16 17:15回复
    分析: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号囚犯存活机率为1-(1/16+1/16)=7/8 

      2号囚犯存活机率:假设2号囚犯摸了n+1颗,后3位囚犯都摸少于n颗的几率为(1/2)*(1/2)*(1/2)=1/8,2号囚犯存活机率为1-1/8=7/8。假设2号囚犯摸了n-1颗,存活机率同样为7/8 

      3号囚犯存活机率:假设3号囚犯摸了目前最多的绿豆数,后2位囚犯都摸少于n颗的几率为(1/2)*(1/2)=1/4,3号囚犯存活机率为1-1/4=3/4。假设3号囚犯摸了目前最少的绿豆数,存活机率同样为3/4 

      4号囚犯存活机率:假设4号囚犯摸了目前最多的绿豆数,最后1位囚犯摸少于n颗的几率为1/2,4号囚犯存活机率为1-1/2=1/2。假设4号囚犯摸了目前最少的绿豆数,存活机率同样为1/2 

      5号囚犯存活机率:5号囚犯摸到的绿豆数不是最大就是最小,存活机率为0 

      但是5号囚犯在必死无疑的情况下,可能会临死拉个一起下水,这样一来,情况就改变了 
      1-4号囚犯策略如前,则4个囚犯摸到的绿豆数为4个连续整数,而5号囚犯摸到的绿豆数必须为4个连续整数的中间两个中的一个,这样有4人必死,只有1人存活 

      1号囚犯存活机率:1号囚犯摸到的绿豆数最大或最小则必死。1号囚犯摸到的绿豆数为最大时的机率为(1/2)*(1/2)*(1/2)=1/8,最小时的机率也为1/8,1号囚犯存活机率为1-(1/8+1/8)=3/4 

      2号囚犯存活机率:假设2号囚犯摸了n+1颗,后2位囚犯都摸少于n颗的几率为(1/2)*(1/2)=1/4,2号囚犯存活机率为1-1/4=3/4。假设2号囚犯摸了n-1颗,存活机率同样为3/4 

      3号囚犯存活机率:假设3号囚犯摸了目前最多的绿豆数,后1位囚犯摸少于n颗的几率为1/2,3号囚犯存活机率为1-1/2=1/2。假设3号囚犯摸了目前最少的绿豆数,存活机率同样为1/2 

      4号囚犯存活机率:4号囚犯摸到的绿豆数不是最大就是最小,存活机率为0 

      再考虑5号囚犯 
      由于5号囚犯摸到的绿豆数必为4个连续整数的中间两个中的一个,故1-3号囚犯存活机率都将减半,即1、2号囚犯存活机率为(3/4)*(1/2)=3/8,3号囚犯存活机率(1/2)*(1/2)=1/4 

      综上所述,1、2号囚犯存活机率最大


    2楼2008-02-16 17:17
    回复
      • 124.133.70.*
      那么复杂的算法亏你想的出!佩服!可是要结合到现实中吧?1号先抓无论多少2号都可以知道他所抓的数量!假设1号拿1颗!那么他是最小的,结果就是死。如果拿2颗结果相同!但是如果抓过6颗那后面的2、3、4、5号都会少于他结果还是死所以无论怎么抓都不可能活下来!
      2号假设1号抓了2颗,那么就剩98颗,他只要抓3颗就基本可以存活下来,因为后面的人无法再抓3颗,除非他自己想死。
      那么2、3都没有了!到3号就只有95颗,除以2每人2.5,但是无法抓半颗!所以只能是有人抓了2颗有人抓了3颗,那么他抓4颗就可以了,到4号依照上面的算法就知道各自抓了多少,所以他必须抓5颗,如果抓6颗,那么5号抓5颗自己则是最多的。所以最简单的算法是1、5必死!题目中说的很明确,1他们都是聪明人2原则是先保命后杀更多的人,也就是说保命和杀更多的人可以同时进行,条件没有限制要抓的数量,只要不少于1即可!所以1号应该全都抓完,其他人都是最少的,也都是相同的数字!所以结果是全死!


      3楼2009-04-12 13:53
      回复