100囚徒难题

oboe

希望楼主能总结一下。
18楼的答案不是最后的答案。

因为它假设了一个条件：
A开灯以后，马上就被关掉，之后轮到A是要100天的概率。
事实上未轮到的人关灯，是1%机会；之后再要A来开灯也要一个%1的机会。
而且前几天未轮到的人狠多，后面却是大部分人都轮过了，

另外请版主编辑一下二楼的贴子，
否则总有无聊的跟贴。

dinhao12345

a m  简单？

白虎

…………………………………………………………………………回复

lwn199287

顶个~~~~~~~~~~~

菜头

顶～～～～～～～～～

lulijie

我的方案：
灯原先关着，
    从放风开始的第1天至第99天，第一次放风的人不作任何动作，第二次放风的人若看见灯关着，就把它打开，记住今天是放风的第几天，比如第N天，那么总共放过风的人数为N-1，以后都由他计数，第二或更多次放风的人若看见灯开着，那么他不作任何动作。  
    放风开始的第100天，放风的人若看见灯关着，那么他可向国王宣布，所有的人都放过风；若看见灯开着，就把灯关闭；若是计数的人放风，则让灯开着。放过风且看见过灯关着的人，也让灯开着。
    放风开始的第101天以后放风，前99天里放过风的人且看见过灯关着的人，他不作任何动作；其他人看见灯关着不作动作，看见灯开着则把它关闭；计数的人看见灯关着，就把它打开，往放过风的人数里加1，看见灯开着，不作动作。关过灯的人，以后放风都不作动作。
    当计数的人将放过风的人数统计到100时，就可向国王宣布，所有的人都放过风。
-------------------------------------------------------------------------------------------------------------
上述方案有个思考不周的地方，现改正如下（红字为修改地方），不影响计算机计算结果（因为前99天放风的人恰好都只放1次风的概率非常非常低。）：
灯原先关着，
    从放风开始的第1天至第99天，第一次放风的人不作任何动作，第二次放风的人若看见灯关着，就把它打开，记住今天是放风的第几天，比如第N天，那么总共放过风的人数为N-1，以后都由他计数，第二或更多次放风的人若看见灯开着，那么他不作任何动作。  
    放风开始的第100天，放风的人若看见灯关着，而他没放过风，那么他可向国王宣布，所有的人都放过风，若他放过风，那么他就是第一个放两次风的人，总共放过风的人数为99，以后都由他计数，让灯开着；若看见灯开着，就把灯关闭；若是计数的人放风，则让灯开着。放过风且看见过灯关着的人，也让灯开着。
    放风开始的第101天以后放风，前99天里放过风的人且看见过灯关着的人，他不作任何动作；其他人看见灯关着不作动作，看见灯开着则把它关闭；计数的人看见灯关着，就把它打开，往放过风的人数里加1，看见灯开着，不作动作。关过灯的人，以后放风都不作动作。
    当计数的人将放过风的人数统计到100时，就可向国王宣布，所有的人都放过风。

[ 本帖最后由 lulijie 于 2009-1-17 17:13 编辑 ]

wyn1992

好呀,期待答案!

cyz

很复杂%%数学真的不好…………

lulijie

按照206#的方法，用计算机模拟放风过程，试验1000次。平均时间是9341天，约25年多。其中几次试验的天数如下：
8573，9589，8064，11437，8255，9869，9087，9698，9373，9509，
9151，10462，10491，10223，10554，9891，7397，9943，9042，9726，
9449，9030，7128，10534，10743，7561，12835，8911，9519，9996，
10534，10332，8170，8834，9235，10508，8860，11555，10136，9281，
7454，9457，8226，7526，7504，10107，8823，11165，9646，10873，
8556，8536，12418，9789，9152，9733，8179，8498，10262，8833，
7719，9631，6812，7772，8121，10806，10362，6465，9514，10240。
------------------------------------------------------------------------------------------------------
按照18#的方法，用计算机模拟放风过程，试验1000次。平均时间是10459天，约28年多。其中几次试验的天数如下
11787，9298，10309，9171，11483，10524，11392，9715，10532，9078，
10541，10494，11460，9269，9627，9948，11295，10989，11969，9883，
9580，9971，10485，10064，11795，9564，10424，11813，11029，9464，
11004，12088，8810，9175，11377，11713，10682，9646，10816，10862，
11225，10905，9721，11809，10973，13235，11202，10623，11089，12388，

[ 本帖最后由 lulijie 于 2009-1-17 15:43 编辑 ]

lulijie

用电脑模拟，各试验1000次。
100天后，100个囚徒全部放过风的次数为  0次
200天后，100个囚徒全部放过风的次数为  0次
300天后，100个囚徒全部放过风的次数为  3次
400天后，100个囚徒全部放过风的次数为  146次
500天后，100个囚徒全部放过风的次数为  506次     （概率差不多为50%）
600天后，100个囚徒全部放过风的次数为  758次
700天后，100个囚徒全部放过风的次数为  898次
800天后，100个囚徒全部放过风的次数为  959次
900天后，100个囚徒全部放过风的次数为  991次
1000天后，100个囚徒全部放过风的次数为  997次
1100天后，100个囚徒全部放过风的次数为  996次
      1000天以后的概率基本上都在99.5%以上。
故若囚徒等不了20多年，可以赌博：1000天时（不到3年）告诉国王，全部放过风。
成功的概率大于99.5%  。