全部版块 我的主页
论坛 经济学论坛 三区 博弈论
3446 9
2012-12-19
题目如下:国王招来100个囚犯,对他们说:
你们犯的是死罪,本应该将你们统统杀掉,但我慈悲为怀,给你们一次求生的机会。15分钟以后,你们将被关进一个有100间隔离牢房的监狱里,每人一间牢房,都与外界隔绝,什么也听不见、看不到,连时间都没法计算,更别说获得外界的任何信息。(送饭除外,但也是不规律的送)
这所监狱有一个院子,每天会随机(注意是完全随机)打开一间牢房的门,让那个囚犯到院子里来放风。院子里有一盏路灯,放风的囚犯可以控制它的开关,将它打开或是关闭。除囚犯之外,其他人都不会去碰开关。这盏灯会永远有充足的
能源供应,如果灯泡坏了或是电路出了故障会马上修好,当然修理人员不会改变灯的状态(开或关)。除了开关这盏灯,放风的囚犯放风时留下的任何其它痕迹
都会在夜晚被清除干净(包括在灯上作的任何记号)。
好了现在我向你们提出一个要求,只要你们做到了,就可以全部获得释放:
若干天以后,你们中只要有任何一个人能够向我证明所有的人都曾到院子里去过,你们就全体释放。当然要有证据!因为我只会给你们一次机会,如果向我证明的那个人无法自圆其说,你们就全部砍头。所以,要珍惜这次机会。如果你们永
远做不到我的要求,你们就全部关到死。
现在给你们15分钟商量你们的方案。15分钟以后,你们将被关进我刚才说的那个监狱,永远无法再交流。
假设你就是100个囚犯中的一个,15分钟你能想出什么样的方案呢?
二维码

扫码加我 拉你入群

请注明:姓名-公司-职位

以便审核进群资格,未注明则拒绝

全部回复
2012-12-20 09:25:47
沙发自己坐。没人知道么?

ZT答案
[zt]
第一天出来的这个囚徒负责关灯,以后出来的囚徒:
1)当灯是关着的时候,如果他没有开过灯,那他可以打开灯,否则他不能开灯;
2)当灯是开着的时候,他不动灯。
3)第一个囚徒在他放风的时候,如果发现灯是开的,那么他就关闭灯。这时他就把放过风的囚徒数加一。
当第一个囚徒的计数达到99的时候(加上他自己是100),他就可以宣布所有的囚徒都放过风啦,按平均计算100×99=9900天,就是27年呀!


[zt]
第二个方法分两个阶段:
阶段一:前100天决定谁来计数。
1)第1-99天,初始灯关着,第一个两次放过风的人将成为计数者,并将灯关上。设其为第K天第2次放风,则他知道已经有k-1个人放过风,做为100天后计数的初始值。
2)第100天放风的人如果看见等关着,则宣布所有人都放过风;否则把灯关上
阶段二:100天后
1)如果计数者放风看见灯开着,则将放过风的人数加1,到100时宣布胜利
2)其他人如果以前没放过风,并且灯关着,则开灯,否则不动
此方法期望年数为24.42年

[zt]
第三种方法提示如下:分为一个基本记数者和N个2级记数者,基本记数者的独立记数上限Cp和2级记数的独立计数上限Cs,时间由长度为S1和S2的两段交替组成.在S1阶段,计数者计数直到达到其独立计数上限,在S2阶段,达到计数上限的2级计数者将通过开灯方法告诉基本计数者直到基本计数者得到所有2级计数者完成任务并加上自己计数为100时宣布自由.
此方法通过计算机模拟优化可在10年左右完成.
二维码

扫码加我 拉你入群

请注明:姓名-公司-职位

以便审核进群资格,未注明则拒绝

2012-12-20 10:02:09
这么折腾死了算了

这所监狱有一个院子,每天会随机(注意是完全随机)打开一间牢房的门,让那个囚犯到院子里来放风。

------- 根据这个条件,没有确定的一个最长周期可以保证所有囚徒都出来过一次。即100个囚徒全部放一次风的可能性太小了。所以说个30年-40年的先拖延时间,然后挖洞逃出去比较好。没逃出去也活差不多活够了。
二维码

扫码加我 拉你入群

请注明:姓名-公司-职位

以便审核进群资格,未注明则拒绝

2012-12-21 16:11:48
楼主分享这道题目的目的不外乎给大家分享下思考问题的方式(或者供大家娱乐一下),如果非要和实际扯在一起,那还有什么意思,当然我们也说要应用于实践,但是我们用的是他的分析方法,而不是完全的生搬硬套
二维码

扫码加我 拉你入群

请注明:姓名-公司-职位

以便审核进群资格,未注明则拒绝

2012-12-26 16:38:25
siegi 发表于 2012-12-20 09:25
沙发自己坐。没人知道么?

ZT答案
大哥,你方法三太NB了!!!还电脑模拟优化,只有十五分钟还是一群囚犯,你真有想象力。。。。。
二维码

扫码加我 拉你入群

请注明:姓名-公司-职位

以便审核进群资格,未注明则拒绝

2012-12-27 08:48:54
随机的就麻烦了哦。感觉好难理清。
二维码

扫码加我 拉你入群

请注明:姓名-公司-职位

以便审核进群资格,未注明则拒绝

点击查看更多内容…
相关推荐
栏目导航
热门文章
推荐文章

说点什么

分享

扫码加好友,拉您进群
各岗位、行业、专业交流群