百囚困境

135087

有100个无期徒刑囚徒,被关在100个独立的小房间,互相无法通信。每天会有一个囚徒被随机地抽出来放风,随机就是说可能被抽到多次。
放风的地方有一盏灯,囚徒可以打开或者关上,除囚徒外,没有别人会去动这个灯。每个人除非出来防风,是看不到这个灯的。
某天,全体囚徒大会,国王大赦,给大家一个机会:如果某一天,某个囚徒能够明确表示,所有的囚徒都已经被放过风了,而且的确如此,那么所有囚徒释放;如果仍有未被放过风,那么所有的囚徒一起处死。
囚徒大会后给大家充分时间讨论,囚徒们能找到方法么?方法要求不会有被处死的危险且早晚会被释放

（答案就是和开关灯有关）
请说明清楚办法（我有个办法，但可能不是最优，欢迎集思广益）

145752

设：
1.讨论时得知未放过风的人数为N。
2.此时未放过风的人属于W，已放过风的人属于F。
3.当W中有人点亮过灯后就从W中移出归于F。
4.开始前先保证灯是关闭的。

方法一：
定一个W中的人a来负责。
W中的人（除了a）在放风时点亮灯，若灯已亮则不动灯。
F都不可动灯。
当a放风时看到已经亮的灯就关上灯。
当a看到灯点的次数是N-1时，加上他自己就是N个，这时a就可以确认大家都放过风了。
（就是废时间）

方法二：
（已编辑）

135087

目前的最优方案（如有新方法随时更新）

设：
1.讨论时得知未放过风的人数为N。
2.此时未放过风的人属于W，已放过风的人属于F。
3.当W中有人点亮过灯后就从W中移出归于F。
4.开始前先保证灯是关闭的。
5.设定第三天放风的人为计数员a

第1天，灯灭状态，此人归于F
第2天，如是第一天的那人，保持灯灭，如是不同人打开灯，此人同样归于F
于是第3天，a就可以从灯明灭判断进行计数（可能性为123,1的话就是三天都是a本人在放风）并关灯或保持灯灭

之后
W中的人（除了a）在放风时点亮灯，若灯已亮则不动灯。
F都不可动灯。
当a放风时看到已经亮的灯就关上灯。
当a计数至100，就可以通报国王。

136614

1.大会之后讨论完囚徒们还有彼此接触交换讯息的机会吗。
2.你的问题是提高囚徒被轮流放风（而不是一人被抽中多次）的机会，还是说自然概率情况下，想办法让别人知道自己放过风了，当所有人都放过风后。就可以有人来宣布了？

153653

应该是和开关灯有关系吧

134917

直接在开灯的地方刻记号，记号达到100时报告

140774

每一个囚犯在一天中第一次出去放风时开一次灯，在灯亮过一百次之后所有人都明白每个人都放过风了。如果是理性人，就算不互相沟通这也应该是每个人都会想到的，讨论之后就更是了。这样一来迟早有一天每个人都放过一次风，不过也许在那之前每个人都死了

135087

所以问题不只是要解题，还要如何最优化，缩短时间 ，基础答案已出

153795

对6楼方案的细节优化：
首先，把灯泡卸下来。
每个人出来放风时可以把灯泡安上去看看有没有亮，但如果不是a还得把灯泡卸下来。
如果100人大会前均未放风：
第一天放风的人直接进入F。
第三天以后看到灯亮的人成为a，不用卸灯泡。
当a看到灯点的次数是96时，把灯砸坏。
W中倒数第二人把坏掉的灯泡卸下来。
W中最后一人看情况可以直接报告了。
如果只有N人需要放风：
第二天以后看到灯亮的人成为a。
当a看到灯点的次数是N-3时，把灯砸坏。

121017

放过风的人开灯，没放过风的人不动灯。大会得知未放风人数A，以A天为周期，每一周期最后一天放风的囚犯查看灯，若此囚犯看见灯未亮，且自己在此周期内未放过风，也不是大会前方过风的，则该囚徒告知。否则继续下一周期。
补充：周期第一位重置灯，使灯关闭。然后，再按上述条件执行。
成功概率是A/100×A-1/100×...×1/100。