Re: [問題] 囚犯和燈

[SJame (小戴)]

※ 引述《Nanan (安慶程二)》之銘言：
: 100個囚犯，101間牢房，每人一間，
: 剩下的那間牢房里面有一盞燈
: 每天隨机叫一個囚犯去空房間一次，可以開燈，關燈，或者什么都不作
: 如果有一天，有一個囚犯說，我确定100個囚犯全都來過了
: 對了，就放了所有囚犯；
: 錯了，就全殺。
: 所有囚犯都看不見燈，除非走進空房間
: 囚犯之間不能互通消息，除非用燈
: 游戲開始之前所有囚犯一起商量一個辦法判斷所有人都進過空房間了
: 請問。。。。。。
在100人中選出一人作為"開燈者"
其他99人作為"關燈者"
分配任務如下:

開燈者的任務:
每次進房時,若燈為暗的,則開燈
           若燈為亮的,則什麼也不做

關燈者的任務:
每次進房時,若燈為暗的,則什麼也不做
           若燈為亮的,則關燈
           但是注意,在第一次執行"關燈"之後,改變任務內容
           變成每次進房時不管燈是亮是暗,什麼都不做

也就是說,只有開燈者可以開燈
也只有關燈者可以關燈,但只能關一次

接著,考慮開燈者的情況
當開燈者第一次進房時,燈一定是暗的,照任務內容將它打開,離開
第二次進房時,若燈是暗的,代表有一個關燈者來過了
往後每一次進房時,若燈是暗的,代表有一個"新的"關燈者進來過
                 若燈是亮的,代表沒有"新的"關燈者進來過

當他確定有99個關燈者進來過時
就可以確定全部來過了

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.114.209.36
推 DKer:高手@@
推 blackneko:就是開燈者開了第100次燈就可以確定了
推 longw:唔  要好多年說
推 libooo:真是高手阿  我只想的到用100天當週期 如果中途
→ libooo:有人進去兩次就把燈關上  第一百個就能判斷了
推 possiblepig:可是是"每天隨機一人進房間"耶
推 nightcatman:沒考慮到在99人次內有人可能被重複叫的問題
推 nightcatman:原po的方法才是正解