全部版块 我的主页
论坛 经济学论坛 三区 博弈论
3278 13
2012-09-05
偶然看到楼主的这个贴,觉得挺有趣,仔细想了想,本人给出不同于楼主的分析方法:
       鉴于原帖回复人数太多,担心回复被淹没,所以重新发一贴讨论,欢迎指正,也敬请谅解。
以下是原帖链接:
       https://bbs.pinggu.org/thread-1148035-1-1.html
       原楼主的原文:
       5 个囚犯,分别按1-5号在装有100颗绿豆的麻袋抓绿豆,规定每人至少抓一颗,而抓得最多和最少的人将被处死,而且,他们之间不能交流,但在抓的时候,可以摸出剩下的豆子数。问他们中谁的存活几率最大??
      提示:
      1,他们都是很聪明的人
      2,他们的原则是先求保命,再去多杀人
      3,100颗不必都分完
      4,若有重复的情况,则也算最大或最小,一并处死
嘿嘿,这是微软的面试题。。。
我解了个答案,不知道对不对,回复那个帖子没人看,所以我又开一个,急切希望高手指正,
我从来没做过这种题,也不懂博弈,只是推理的,不知道对不对。
本文来自: 人大经济论坛 博弈论 版,详细出处参考: https://bbs.pinggu.org/forum.php?mod=viewthread&tid=1148035&page=1&from^^uid=3338697
        原楼主的的回复:
        1:前提 最少死两个 最多和最少 必须要死 一样的也得死 一样的越多死的越多  最多全死 一人20个
最少一人拿一个 所以第一个人必须留出4个
一号 100-4=96 超过48必死  拿一个必死 2个也不安全 所以最中间的数是最安全的  
一号选拿24
二号要求必须小于24  100-24=76
假设二号拿25个 100-24-25=51
三号拿23        100-24-25-23=28                                                               
四号拿23必死 所以只能拿22 五号剩一个                                                           
二号和5号必死                                                                                 
                                                                                               
2:所以一下任何人不敢超过24个 如果二号拿22个 三号必拿23 所以 23是最安全的 二号选23个            
100-24=76 76-23=53
到三号了 剩53个球  三号拿22个 100-24-23-22=31
四号 31-16=15   31-21=10 所以四号随便拿21-16之间 绝不会死
五号最多拿10-15个 所以五号和一号必死
3:假设大家都算出结果 超过24必死 少于16必死 因为你拿15就会有人拿16 到最后 拿15还是最少
那么还是一样 中间最安全 一号选19 和20个
假设
一号选20个 其实20和19都是一样的
二号 100-20=80
假设二号大于20  拿21个
三号80-21=59 三号拿19个
四号59-19=40  四号拿18个
五号40-18=22 五号最多22个
那么5号必死
得出结论五号怎么拿还是死 就看和二号一起死 还是和4号一起死
得出结论 如果谁大于20号 也是有机会必死的 是和5号一起死的

4:情况又变了 超过20必死 低于18必死,那么取中间 一号还是拿19了
那么结果还是一样 二号拿18 三号拿17 四号拿16 五号怎么都是死 就看跟谁死 谁若超过一号 谁就有机会和五号一起死所以没人敢超过一号
也许有人会问 3号之前有两个人拿过球 如何知道他们拿多少 而只比2号少拿一个,题目有的 可以摸清剩下多少球
如果前面假设正确,那么把100减去剩下的球,就是他们两人拿走的球,把拿走的球除以2就得出他们每人拿走多少球,可是却剩一个球没除开
这个球就是一号的。
5:假设 一号只拿5个球 二号拿4个 三号拿3个 四号拿2个 结果还是一样 五号还是必死 就看和谁一起死。
   以上来看 一号好五号死的几率是最大的。
6:但是情况又变了
   假设一号只拿4个球,二号拿3个 三号不可能拿2个 因为没人会拿一个 三号拿5个 四号只能拿6个或者2个,结果都是一样。 那么五号还是必死 和谁一起死 将决定他和四号怎么拿,这就不用解释了吧
   这回一号最安全了 拿4个球 怎么都不会死的了
7:如果一号拿3个 二号拿两个 因为没人会拿1个 所以二号拿2个就会死 二号会拿4个,三号拿5个 四号拿6个也好2个也好 都是会由五号来选和谁一起死
  
   如果一号拿3个 二号拿4个 三号拿2个 四号拿5个 五号还是必死 和三号或者四号 一起死  
所以 一号拿4个 是最安全的,五号必死。二号只要贴着一号就是最安全的,一号拿大于4的时候就比一号少拿一个 一号拿少于4的时候 就比一号多拿一个
   结果就是一号好二号最安全
   不知道对不对 有不对的地方请提出,解了快两个小时了。
本文来自: 人大经济论坛 博弈论 版,详细出处参考: https://bbs.pinggu.org/forum.php?mod=viewthread&tid=1148035&page=1&from^^uid=3338697
        文章太长了,所以本人将以回复的形式来解答这个问题。敬请谅解。

二维码

扫码加我 拉你入群

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

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

全部回复
2012-9-5 21:06:13
假设一次抓豆的五个人分别为A,B,C,D,E。
每个人决策的约束条件:
1、        尽可能确保自己抓到的豆数不是最少;
2、        尽可能确保自己抓到的豆数不是最多;
3、        尽可能确保自己不和别人抓到一样多的豆子;
4、        考虑别人决策对自己的影响,尽可能避免被别人有意设陷处死。

现在,我们开始逐个分析每个人的决策:
A,        先抓。
首先,确保自己抓到的不是最少的。
1个豆最少,必死无疑;每个人都会这么想。
这样就没有人抓一个豆,2个豆成为最少,抓2个豆必死无疑;
这样就没有人抓两个豆,3个豆就会成为最少,抓3个豆必死无疑;
一次类推,但抓到多少豆子才能避免自己一定不会成为最多的呢?100个豆子,如果全部抓完,人均20豆,达到平均水平可能就不会成为最少的。
因此,A先抓,抓的最少数量为20个。
其次,确保自己抓到的不是最多的。
50个豆占掉总数一半,若抓50个必死无疑;
50以内的,如果抓数大于34,那么B就会根据A的数量采取设陷策略,紧随A之后,确保A成为最多数,同时自己不会成为最少。例如,A若抓34颗,那么B就会抓33颗,剩余才33颗,A就必死无疑。34颗至100颗之间肯定不会成为A抓豆数的选择。
再次,A要竟可能确保自己和别人抓到的豆子不一样多。因为A先抓,所以,他有先发优势,别人就会主动考虑这个问题。
最后,A要考虑别人的决策对自己的影响,竟可能避免被别人有意设陷阱处死。
A不抓1至19之间的豆子可以主观上避免成为豆数最少的人,但是如何避免成为最多豆子的人?
排除34至100的豆数之后,我们在20至33之间考虑。
由于B可以通过摸清剩余数量而得之A的数量,而C又可以通过摸清剩余数量知道A和B抓豆的总数,因此,A需要避免B和C的默契配合把自己处死。例如,C知道A不会考虑33以上的豆数,而B也知道C能够考虑到这一点,所以,比如说A抓33,而B抓32,总数为65,剩余35,C知道A能够抓的豆数最大为33,而B也知道,因此,若总数为65的话,C能够推知A选择了33,也会采取策略投死A,并且避免D,E和自己相同或者让自己变成最少。
如此,A不能选33,那么最大只能选择32,同样,这会被B和C猜中,因此32不能选择,以此类推……
那么到多少时,B和C就无法通过配合处死自己呢?
直到A选择26时,B还可以采取更随策略选择25,而C则很尴尬,面临和D重复的危险。即便如此,C仍然可以冒一定风险而和B一起做掉A。
A最大数不能超过26,其它人也不傻,不会选择超过26,因此,对A而言26也不是安全数字。
只要A选择的数字超过20,B的最佳策略就是追随A,选择比A 少的数。而且最佳的数就是比A少1个。
如此,A的最佳策略就是抓取 21、20两个数字中的任何一个。
到现在为止,我们只分析了A的决策,未完待续,敬请指正。
二维码

扫码加我 拉你入群

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

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

2012-9-7 15:58:09
A的最佳策略就是先摸取 21颗或者20颗豆子,A的策略B/C/D/E四人必然能够猜到。
B紧随A之后,我们来分析B会采取什么策略。
情况1:当A选了21时,B若选却超过21的豆数,在C看来,无论A还是B超过21就有被设陷处死的可能,因此,B绝不会选取超过21的豆数,当然,他也不会选21。此种情况下,他的策略就是选择小于A的豆数,同时又尽量避免成为豆最少的人,当A选了21颗时,剩下79颗豆子,4人平均19.75颗,大于等于平均数,就绝对不会成为豆数最少的人,因此,此时他的最佳策略就是选20颗。
若B选20颗,则C的策略就是选19,剩余40颗归D和E选,假如D选18,E就必死无疑,而E若必死,则会拉人下水,21最大,18最小,他会选择20和19中的任何一个,同归于尽。若是这样,D也就必死了,那么D也会托人下水,所以,D 就会改变主意,选择20,而E也必然会选20或者19,结果还是大家同归于尽。
总结:
    从A到E以此都有优势策略,最终E必死,反过来,E在必死的情况下,又有拖他人下水的策略,逆推之后,大家的选择最终是同归于尽。
二维码

扫码加我 拉你入群

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

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

2012-9-7 16:05:43
上边分析的有点长也有些乱,在这里总结一下,5个人同归于尽的分析思路:从A至E,无论怎么选,总是有人必死,有人必死的原因就是他人采取了优势策略,因此,后发选择必死的人就会基于自己必死的前提做出尽可能拖别人下水的策略。逆推就是,E必死,既然若此,他会拖至少1人处死,那么这个人也会再拖至少1人下水,若此,A就没有优势策略了,大家都会死。
最终结论:五个人同归于尽。

二维码

扫码加我 拉你入群

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

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

2012-9-10 09:19:05
感谢楼主分享
二维码

扫码加我 拉你入群

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

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

2012-9-10 09:56:30
百目庆 发表于 2012-9-10 09:19
感谢楼主分享
欢迎批评指正哈
二维码

扫码加我 拉你入群

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

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

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

说点什么

分享

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