找回密码
 立即注册
搜索
总共850条微博

动态微博

查看: 1735|回复: 2
打印 上一主题 下一主题
收起左侧

100 prisoners problem(zt)

[复制链接]

2

主题

16

帖子

170

积分

跳转到指定楼层
楼主
发表于 2006-2-26 10:13:48 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式

There are 100 prisoners in solitary cells. There's a central living room with one light bulb; this bulb is initially off. No prisoner can see the light bulb from his or her own cell. Everyday, the warden picks a prisoner equally at random, and that prisoner visits the living room. While there, the prisoner can toggle the bulb if he or she wishes. Also, the prisoner has the option of asserting that all 100 prisoners have been to the living room by now. If this assertion is false, all 100 prisoners are shot. However, if it is indeed true, all prisoners are set free and inducted into MENSA, since the world could always use more smart people. Thus, the assertion should only be made if the prisoner is 100% certain of its validity. The prisoners are allowed to get together one night in the courtyard, to discuss a plan. What plan should they agree on, so that eventually, someone will make a correct assertion?
www.ddhw.com

 
回复

使用道具 举报

1177

主题

2775

帖子

6万

积分

沙发
发表于 2006-2-26 12:31:31 | 只看该作者

回复:100 prisoners problem(zt)


一道类似的题目很久以前这里讨论过。
 
zyang131®的题有一点点不同:如果犯人知道那盏灯炮的起始状态(OFF),那么该题就容易些;如果犯人不知道那盏灯炮的起始状态,那么该题就跟以前讨论的那题难度一样了。
 
因为这里有许多新来的朋友,为了方便起见,我把那道中文版本的题目转过来,没有做过的朋友们可以讨论。这道题目非常好。
 
————————————————————————————
 
监狱的管理者一天告诉监狱里的 23名犯人:

今天你们所有的人可以在一起碰一次面(交流,讨论)。从明天起,你们将被分开关在各自的房间里,你们将没有机会交流,没有机会碰面。www.ddhw.com

那边有一间电器控制室,里面有2个开关 A 和 B ( 象正常的电灯开关一样,A 和 B 都有 “开”和“关”的位置以及“开”和“关”的标签)。我不告诉你们现在 A,B 开关的状态(开或关)。 开关 A 和 B 纯粹是一个开关,他们不控制任何电器。

从明天起,我每隔一段时间会随机的从你们23人中,选一个人去那间电器控制室,他可以挑选一个开关,改变状态。比如说,挑选了开关 A ( 如果 A 是 开的状态,他可以让 A 转到 关的状态;如果 A 是关的状态,它可以让 A 转到 开的状态)

然后,他将回到自己的房间。除了这里的犯人之外,没有任何其他人能碰到电器控制室里的 A,B 开关。

所以最终你们所有的犯人,将有机会改变电器控制室里的开关。

在任何时候,如果你们当中有人向我宣布“我们所有的人都至少有一次改变了电器控制室里的开关”

如果,这句话是正确的,那我将让你们所有的人重获自由;
如果不对(那就是,只要有人未曾去过电器控制室),你们所有的人将被处死。

现在,你为犯人们设计一个好的方案,让他们尽早释放。
www.ddhw.com

 
回复 支持 反对

使用道具 举报

210

主题

3101

帖子

8万

积分

板凳
发表于 2006-3-2 12:45:42 | 只看该作者

zyang131, 对不起,你在导弹多久可以击中敌机题下对我的问刚才才看到.......


答在那了,也不知是否一定对.
www.ddhw.com

 
回复 支持 反对

使用道具 举报

24小时热帖
    一周热门
      原创摄影
        美食美文
          您需要登录后才可以回帖 登录 | 立即注册

          本版积分规则

          Archiver|手机版|珍珠湾ART

          Powered by Discuz! X3 © 2001-2013 All Rights Reserved