经管之家App
让优质教育人人可得
立即打开
全部版块
我的主页
›
论坛
›
经济学论坛 三区
›
博弈论
灯和囚犯,最佳答案是什么
楼主
siegi
3446
9
收藏
2012-12-19
题目如下:国王招来100个囚犯,对他们说:
你们犯的是死罪,本应该将你们统统杀掉,但我慈悲为怀,给你们一次求生的机会。15分钟以后,你们将被关进一个有100间隔离牢房的监狱里,每人一间牢房,都与外界隔绝,什么也听不见、看不到,连时间都没法计算,更别说获得外界的任何信息。(送饭除外,但也是不规律的送)
这所监狱有一个院子,每天会随机(注意是完全随机)打开一间牢房的门,让那个囚犯到院子里来放风。院子里有一盏路灯,放风的囚犯可以控制它的开关,将它打开或是关闭。除囚犯之外,其他人都不会去碰开关。这盏灯会永远有充足的
能源供应,如果灯泡坏了或是电路出了故障会马上修好,当然修理人员不会改变灯的状态(开或关)。除了开关这盏灯,放风的囚犯放风时留下的任何其它痕迹
都会在夜晚被清除干净(包括在灯上作的任何记号)。
好了现在我向你们提出一个要求,只要你们做到了,就可以全部获得释放:
若干天以后,你们中只要有任何一个人能够向我证明所有的人都曾到院子里去过,你们就全体释放。当然要有证据!因为我只会给你们一次机会,如果向我证明的那个人无法自圆其说,你们就全部砍头。所以,要珍惜这次机会。如果你们永
远做不到我的要求,你们就全部关到死。
现在给你们15分钟商量你们的方案。15分钟以后,你们将被关进我刚才说的那个监狱,永远无法再交流。
假设你就是100个囚犯中的一个,15分钟你能想出什么样的方案呢?
扫码加我 拉你入群
请注明:姓名-公司-职位
以便审核进群资格,未注明则拒绝
全部回复
沙发
siegi
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年的先拖延时间,然后挖洞逃出去比较好。没逃出去也活差不多活够了。
扫码加我 拉你入群
请注明:姓名-公司-职位
以便审核进群资格,未注明则拒绝
板凳
liuxiang0701
2012-12-21 16:11:48
楼主分享这道题目的目的不外乎给大家分享下思考问题的方式(或者供大家娱乐一下),如果非要和实际扯在一起,那还有什么意思,当然我们也说要应用于实践,但是我们用的是他的分析方法,而不是完全的生搬硬套
扫码加我 拉你入群
请注明:姓名-公司-职位
以便审核进群资格,未注明则拒绝
报纸
243671744
2012-12-26 16:38:25
siegi 发表于 2012-12-20 09:25
沙发自己坐。没人知道么?
ZT答案
大哥,你方法三太NB了!!!还电脑模拟优化,只有十五分钟还是一群囚犯,你真有想象力。。。。。
扫码加我 拉你入群
请注明:姓名-公司-职位
以便审核进群资格,未注明则拒绝
地板
hawching
2012-12-27 08:48:54
随机的就麻烦了哦。感觉好难理清。
扫码加我 拉你入群
请注明:姓名-公司-职位
以便审核进群资格,未注明则拒绝
点击查看更多内容…
7楼
惊鸿踏月
2012-12-28 10:34:20
概率问题,囚犯要实践起来很难的
扫码加我 拉你入群
请注明:姓名-公司-职位
以便审核进群资格,未注明则拒绝
8楼
siegi
2012-12-30 21:03:59
其实我觉得第一个方法拓展一下,可能还能缩短一半的时间
扫码加我 拉你入群
请注明:姓名-公司-职位
以便审核进群资格,未注明则拒绝
9楼
王祥
2013-1-5 11:30:22
要想超越别人,就不要纵容自己
扫码加我 拉你入群
请注明:姓名-公司-职位
以便审核进群资格,未注明则拒绝
10楼
dogatedog
2013-1-9 19:41:32
按照楼主给的第一个方法可以知道犯人可以串通的话,不就简单了,直接这样:每天到院子里的犯人只要是没出来过的,就先把灯关了再打开,不管灯当时是开的还是关的,出来过的都把灯关上,大家都数一下数到100次灯亮就行了,至于时间到底要多久和概率有关系,不好说
扫码加我 拉你入群
请注明:姓名-公司-职位
以便审核进群资格,未注明则拒绝
相关推荐
十个囚犯的难题,开动你的脑筋?!(推理游戏)
[讨论]如何学好政治,十金征求最佳答案.
本论坛可否设个最佳答案
电脑类型推荐
房价算不算物价
请问怎么把悬赏给别人?
如果悬赏的时候,发现有的回答不是最佳答案,但是也想给他一些论坛币,这么给?
求最佳答案
已经有最佳答案的帖子 是不是不能再回复 含附件的内容了
(非求助贴)补偿oyefer坛友
栏目导航
博弈论
CAIE文档助手
休闲灌水
经管文库(原现金交易版)
求助成功区
金融学(理论版)
热门文章
Nature点赞!哈佛MIT最新作:AI科学家时代来 ...
2025新书-Multivariate analysis and machi ...
2025年全行业薪酬报告
国防军工行业2025四季度策略:内需军贸,有 ...
达富发投资关于中百集团行情数据操作分析与 ...
AI智能家庭( AI2H)研究报告 2025
英文书籍
2025年中国汽车品牌出海白皮书
2025 国家级都市圈谁在领跑
和橘子学AI创作【500集120实战】
推荐文章
10月重磅来袭|《打造Coze/Dify专属学术智能 ...
高校老师和学生都在偷偷上的智能体课,到底 ...
最快1年拿证,学费不足5W!热门美国人工智能 ...
关于如何利用文献的若干建议
关于学术研究和论文发表的一些建议
关于科研中如何学习基础知识的一些建议 (一 ...
一个自编的经济学建模小案例 --写给授课本科 ...
AI智能体赋能教学改革: 全国AI教育教学应用 ...
2025中国AIoT产业全景图谱报告-406页
关于文献求助的一些建议
说点什么
分享
微信
QQ空间
QQ
微博
扫码加好友,拉您进群
各岗位、行业、专业交流群