[转帖]100囚徒难题

chenweihua

<>编号不行吧 ，</P>
<>因为彼此不能通信 。</P>

迈特莱豹

<>根据4楼就等到几十年了</P>

mamatong

<>大哥,用概率算所有人被抽出的概率趋近于0吧,真是无期死刑了</P>

cx19860824

<>我发现你们很多人已经假设人的生命是无限长了，其实我门要做的，不只是找到个办法让所有人走，还要考虑到所花时间的期望啊。</P>

郁伽小印

<>取10天为一段，每段第一天第一次到的人如果发现灯灭就打开；每段每天非第一次到的人关灯。</P>
<>每个人都把自己当作观察者，每个人都清楚自己放风的日期，如果一个人发现灯亮就知道该段第一次到的人数，直到加和为100，就可以确定每个人都放过风。</P>

roc_the_red

<>楼上的方法好像不行吧</P>
<>开会以后互相就不能通信了，这样数据掌握在不同人手里，你怎么加呀？</P>

alixender

我看帖的时间就超过20分钟，等死吧！

qpzm89

首先，可以肯定的是所有囚犯100%被释放的方案是不可能有的，因为题意是随机抽取的，有可能永远都只抽到99个囚犯，而且不能叫前99天的人去确定，否则，那就100%会死啦！而我下面提出的方案不确保这是所有方案中的的概率最大，但我可以确保所有囚犯不会全部被处死。方案是：要每个囚犯记住由国王开始大赦的天数，以100天为一个周期，第1天被抽到的囚犯不管灯是什么状态，都要确保灯是处于熄灭状态，而第2天到第99天被抽到的囚犯，如果其中有被抽到第两次或以上的就保证灯处于亮着的状态，而第一次被抽中的就不管灯或者保证灯的状态不变，而到了第100天被抽中的囚犯如果发现灯是处于熄灭的状态，那他就该感谢上帝了！囚犯门全都被释放，而且由这个囚犯来确定所有囚犯都放过风；但如果灯是亮着的，那就等下次吧！而且这个囚犯还要把灯给熄灭。按这种办法重复循环第二个周期，但第二个周期的时间可以适当的减短！
       时间问题也说不了这么多了！

shuizhibai

如果依照你的方法，那要死多少啊！！

clfhhc

我唯一想到的是
如果没有观察员，那就一定要有一个类似计数器来记录总共开灯关灯的次数（否则题就没法做了）。
有了计数器：
从第一天的第一个人放风算起，第一次放风的人就别动那灯， 第二次或以上的放风一天就改变灯的状态一次（开-〉关 或 关-〉开）。 然后等到100+n天时任何一个囚犯看到计数器上刚好记录n次开关就可以去上报了。