强盗分金币详细解答

这是一道微软的面试题目。
还是比较难的,要充分考虑后才可能得到满意的答案
试试看,你能想到吗?
强盗分金币题目:
5个强盗 (按凶狠的程度排序:A,B,C,D,E) 分100个金币。他们设定了一个规则:从A开始分金币的提议,然后剩下4个强盗投赞同或反对票,如果有半数或半数以上的人反对,A就被杀掉,否则就按此提议分;如果A被杀了,接着轮到B提议,然后还是按照上述办法继续下去。
 假设这里每一个强盗都是绝顶聪明的,而且他们的所有行为(提议与投票)都是对自己最有利的。请问这100个金币是怎么分的?每个人各拿多少个?
[解答]1号海盗分给3号1枚金币,4号或5号强盗2枚,自己独得97枚。分配方案可以写成(97,0,1,2,0)或(97,0,1,0,2)。
 推理过程是这样的:
 逆推法:如果1--3号都被扔进了大海,只剩4号和5号的话,5号一定投反对票让4号喂鲨鱼,独吞金币。(因为只要5号不同意,4号提出的方案就无法过半数)所以,4号只有支持3号的方案才能保命。3号知道这一点,会提出(100,0,0)的方案,对4号,5号一毛不拔而将金币全部归为己有,因为他知道4号虽然没得到金币但可以保命还是会投赞成票,在加上3号自己的一票方案就可通过。不过,2号推知3号的方案,就会提出(98,0,1,1)的方案,既放弃3号,而给4号和5号各一枚金币。由于该方案对4号和5号来说比在3号分配时更为有利,他们将支持2号而不希望他出局由3号来分配。这样2号将拿走98枚金币。同样,1号也会洞悉2号的方案而会提出(97,0,1,2,0)或(97,0,1,0,2)的分配方案,既放弃2号,给3号一枚,同时给4号(或5)号2枚。由于1号的方案对于3号和4号(或5号)来说,相比2号分配时更优,他们将投赞成票,加上1号自己的一票,1号的方案既可通过,得到97枚金币,这是能够实现收益最大化的最佳方案了。
当然答案不止一个,还有其他答案。你想想看。
先提示一下两外两个答案:
A:99     B:0     C:0     D:0     E:1   
A:97     B:0     C:1     D:1     E:1 
有好的答案也可以提供一下啊。—》
attachments/200709/3758789993.gif

发表评论

(required)