读取中...
日志搜索
用户登录
读取中...
用户公告
读取中...
时间记忆
读取中...
最新日志
读取中...
最新回复
读取中...
最新留言
读取中...
加入群组
读取中...
我的好友
读取中...
我的照片
囚犯问题 

在网上看到这样一道题目:

 

国王招来100个囚犯,对他们说:你们犯的是死罪,本应该将你们统统杀掉,但我慈悲为怀,给你们一次求生的机会。15分钟以后,你们将被关进一个有100间隔离牢房的监狱里,每人一间牢房,都与外界隔绝,什么也听不见、看不到,连时间都没法计算,更别说获得外界的任何信息。

 

这所监狱有一个院子,每天会随机(注意是完全随机)打开一间牢房的门,让那个囚犯到院子里来放风。其它囚犯不知道。院子里有一盏灯,放风的囚犯可以控制它的开关,将它打开或是关闭。除囚犯之外,其他人都不会去碰开关。这盏灯会永远有充足的能源供应,如果灯泡坏了或是电路出了故障会马上修好,当然修理人员不会改变灯的状态(开或关)。

 

除了开关这盏灯,放风的囚犯放风时留下的任何其它痕迹都会在下次放风时被清除干净(包括在灯上作的任何记号)。

 

牢房是完全封闭的,院子里的灯光在牢房里看不到。只有放风出到院子里的人才能看到。

 

好了现在我向你们提出一个要求,只要你们做到了,就可以全部获得释放:

 

若干次以后,你们中只要有任何一个人能够向我证明所有的人都曾到院子里去过,你们就全体释放。当然要有证据!因为我只会给你们一次机会,如果向我证明的那个人证据不足,你们就全部砍头。所以,要珍惜这次机会。

 

现在给你们15分钟商量你们的方案。15分钟以后,你们将被关进我刚才说的那个监狱,永远无法再交流。

 

应该怎么商量?

 

 

 

 

在网上找到两个还算靠谱的答案:

 

答案1:

他们要进去坐牢的时候选择一个人负责,比如叫A。对他讲好(最好选一个记性比较好的人,因为这样的时间是要很久的): 
“你每次出来只能关灯。其他所有人只能出来开灯一次,就算是你出来灯是关着的,但是你已经开过灯了,那么再也不能开灯了,如果出来灯是关着的,你还没有开过灯就开,是关着的就代表是别人开的,你就不要动。每个人不是第一次出来的话,就不要动灯的开关,就当没有这次出来。所以你每次出来就关灯,如果你出来灯是关着的,那么表示你在你上次出来之后,没有新人出来,所以你这次不要动,不要计数,直到你这样关了100次(如果他是第一次出去的人,而且原来灯就是开着的,那么99次就不够,所以要100次关灯),就代表全部人都出来过了。” 这样可能要20多年的时间。

 

 

那么稍微把题目改一下,

 

…………

 

这所监狱有一个院子,每次会随机(注意是完全随机)打开一间牢房的门,让那个囚犯到院子里来放风,且会在此囚犯回去后立刻放出下一名囚犯,但其它囚犯不知道。院子里有一盏灯,放风的囚犯可以控制它的开关,将它打开或是关闭。除囚犯之外,其他人都不会去碰开关。这盏灯会永远有充足的能源供应,如果灯泡坏了或是电路出了故障会马上修好,当然修理人员不会改变灯的状态(开或关)。

 

…………

 

 

答案2:

100名囚犯中选择一名囚犯A,A负责检查灯泡的状态并且开灯,3种情况,1灯泡开着,不管。2灯泡关着,且是凉的,开灯。3灯泡关着,且是热的,此时加1人,然后开灯。不明白的话等我继续。

 

现在假设,第1个人出来,无论灯泡的初始状态是开还是关,这时第1个人负责把灯泡打开弄热之后再关上,然后第2个第3个第4个人出来,发现灯泡是关闭且是热的,就再把灯打开加热然后关上。以此类推,直到A出来,摸灯泡是热的就加一个人,然后把灯打开。

 

此后,第1个人要是在出来,也有三种情况,若是灯关热,则他开灯加热然后关灯,若灯是关凉,则他不动,若是灯开着,则他关灯且要等到把灯晾凉方才回去。以上谈到两次本来是热的灯泡还要开灯加热再关上,目的是为了A出来摸的时候灯还保持温度。记住,每个人只能做一次把凉灯泡加热的动作,这样A就不会数重复。但是像把热灯泡继续加热保持温度的动作要做很多次。以此类推,只要A数到99个热灯泡的时候就可以向国王汇报了,万无一失,就是时间恐怕长了点。

 

分析一下他的答案,其实是有破绽的。假设有这样一种情况:第1,2,3,4名囚犯连续的出来放风并且都是第一次出来,则都把灯泡加热然后关上,这之后A再出来发现灯泡关着且是热的,加1人,并开灯。接着第2,3,4名囚犯中的任意一人再出来,则关灯且要等到把灯晾凉方才回去,此后A再出来,发现灯泡关着,且是凉的,不计数并开灯;或者A回来后,第5个人接着出来,使灯泡关着且是热的,然后第2,3,4名囚犯中的任意一人再出来,保持灯泡是关闭且是热的,然后A再出来,发现灯泡关着且是热的,加1人,并开灯,然后第2,3,4名囚犯中的任意一人再出来,发现灯开着,则他关灯且要等到把灯晾凉方才回去,此后A再出来,发现灯泡关着,且是凉的,不计数并开灯……此时你就会发现,第2,3,4名囚犯无论再出来多少次都不会被A计数,也就是说A 永远也不会数到99。

连带着的一个问题就是,99名囚犯中的任何一人从第二次出来后都不会遇到灯是关且是凉的,如果此题默许这种情况发生,那么所谓依靠灯关且灯泡是热的作为计数的信号就完全不合理,因为假设当一名囚犯第一次出来加热灯泡后,可能直到灯泡凉了A才被放出来。

 

 

那么再稍微把题目改一下,

 

…………

 

这所监狱有一个院子,每次会随机(注意是完全随机)打开一间牢房的门,让那个囚犯到院子里来放风,且会在此囚犯回去后立刻放出下一名囚犯,但其它囚犯不知道。院子里有一盏灯,放风的囚犯可以控制它的开关,将它打开或是关闭,但每一名囚犯都不可以把灯处于开状态时离开,除囚犯之外,其他人都不会去碰开关。这盏灯会永远有充足的能源供应,如果灯泡坏了或是电路出了故障会马上修好,当然修理人员不会改变灯的状态。

 

…………

 

则答案是不是可以变成这样:

 

100人中选一人负责计数,其余的99人第一次出来时,负责使灯关且灯泡为热的。

 

若这99人中的任何一个人再被放出来时,有两种情况:

1.灯泡是凉的。

此时又分两种情况:a.第一次出来时灯泡是凉的或者是开的,直接回去(防止多数);

b.前一次出来时灯泡为热的,开灯加热后关灯(防止少数)。

但此后若再出现情况b,则直接回去(防止多数)。

 

2.灯泡是热的。开灯加热后关灯。

 

计数的人出来时检查灯泡的状态,若灯关且灯泡为热的,就计数1,之后保持灯关但灯泡为凉的,当计数的人数到99时就可以向国王汇报了.

  • 标签:逻辑,推理 
  • 发表评论:
    读取中...
    Powered by 推理之门.