[智趣推理] 微软著名的面试博弈题--海盗分宝石

５个海盗抢到了１００颗珠宝，每一颗都同样大小和价值连城。他们决定这么分配：首先，抽签决定自己的顺序号码（１、２、３、４、５）；第二步，由１号先提出分配方案，然后５个人进行表决，当且仅当超过半数的人同意时，按照他的提案进行分配，否则他将被扔入大海喂鲨鱼；第三步，１号死后，再由２号提出分配方案，然后４人进行表决，当且仅当超过半数的人同意时，按照他的提案进行分配，否则他将被扔入大海喂鲨鱼；第四步，以此类推。


条件：每个海盗都是很聪明的人，都能很理智的判断得失，从而做出选择。

答案：

[post]这个题目要用逆向递推的方法    首先假设1号、2号、3号的方案都被否决了，他们都被扔海里喂鱼了，剩下4号、5号。 这时候4号只有一种结果：被扔到海里，因为不管他提出什么方案都会被5号否决，他的方案都过不了半数。        现在把3号加进来，不管3号提什么样的方案，4号都必须同意才能保命，所以3号可以把100颗都独吞了。        再把2号加进来，这时时候2号只要给4号、5号每人一颗宝石就能确保方案通过，因为4号和5号清楚地知道，让3号来分的话，他们一颗都得不到，所以2给他们每人一颗的话，就能让他们同意自己的方案，自己可独得98颗。      最后把1加进来，1只要给在2的方案一颗都得不到的3号一颗宝石，给4号或者5号中的任意一个2颗，就能确保方案通过。
所以最终的分配方法是：1号97颗、2号没有、3号1颗、4号两颗、5号没有（或者4号没有，5号两颗）[/post]