作者SJame (小戴)
看板Inference
标题Re: [问题] 囚犯和灯
时间Mon Jul 18 18:46:08 2005
※ 引述《Nanan (安庆程二)》之铭言：
: 100个囚犯，101间牢房，每人一间，
: 剩下的那间牢房里面有一盏灯
: 每天随机叫一个囚犯去空房间一次，可以开灯，关灯，或者什么都不作
: 如果有一天，有一个囚犯说，我确定100个囚犯全都来过了
: 对了，就放了所有囚犯；
: 错了，就全杀。
: 所有囚犯都看不见灯，除非走进空房间
: 囚犯之间不能互通消息，除非用灯
: 游戏开始之前所有囚犯一起商量一个办法判断所有人都进过空房间了
: 请问。。。。。。
在100人中选出一人作为"开灯者"
其他99人作为"关灯者"
分配任务如下:
开灯者的任务:
每次进房时,若灯为暗的,则开灯
若灯为亮的,则什麽也不做
关灯者的任务:
每次进房时,若灯为暗的,则什麽也不做
若灯为亮的,则关灯
但是注意,在第一次执行"关灯"之後,改变任务内容
变成每次进房时不管灯是亮是暗,什麽都不做
也就是说,只有开灯者可以开灯
也只有关灯者可以关灯,但只能关一次
接着,考虑开灯者的情况
当开灯者第一次进房时,灯一定是暗的,照任务内容将它打开,离开
第二次进房时,若灯是暗的,代表有一个关灯者来过了
往後每一次进房时,若灯是暗的,代表有一个"新的"关灯者进来过
若灯是亮的,代表没有"新的"关灯者进来过
当他确定有99个关灯者进来过时
就可以确定全部来过了
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.114.209.36
1F：推 DKer:高手@@ 220.137.76.180 07/18
2F：推 blackneko:就是开灯者开了第100次灯就可以确定了 61.63.39.75 07/18
3F：推 longw:唔 要好多年说218.166.137.181 07/18
4F：推 libooo:真是高手阿 我只想的到用100天当周期 如果中途 203.203.36.250 07/20
5F：→ libooo:有人进去两次就把灯关上 第一百个就能判断了 203.203.36.250 07/20
6F：推 possiblepig:可是是"每天随机一人进房间"耶 59.116.75.50 07/28
7F：推 nightcatman:没考虑到在99人次内有人可能被重复叫的问题 61.228.74.50 08/19
8F：推 nightcatman:原po的方法才是正解 61.228.74.50 08/19