微软面试智力题

Question

10个海盗抢到了100颗宝石，每一颗都一样大小且价值连城。他们决定这么分： （1）抽签决定自己的号码（1~10）； （2）首先，由1号提出分配方案，然后大家表决，当且仅当超过半数的人同意时，按照他的方案进行分配，否则将被扔进大海喂鲨鱼； （3）如果1号死后，再由2号提出分配方案，然后剩下的4个人进行表决，当且仅当超过半数的人同意时，按照他的方案进行分配，否则将被扔入大海喂鲨鱼； （4）依此类推…… 条件：每个海盗都是很聪明的人，都能很理智地做出判断，从而做出选择。 问题：第一个海盗提出怎样的分配方案才能使自己的收益最大化？

Answer 1

还是用倒推法:1.9号要活命,唯一的方法是不让自己提案,所以他会无条件同意8号的方案,因此,8号的方案是自己独得;2.7号需要3票,是拿不到8号的票的,因此除了自己一票外,还需要9,10同意,因此方案是98/0/1/1;3.6号还是3票,给8号一个,9号和10号随便一个给2个,方案是97/0/1/2/0或97/0/1/0/24.5号需要4票,给7号1个,再给9号和10号1人1个,(因为在6号的方案中,两个人都不能肯定自己得到,因此会同意5号的方案),方案是97/0/1/0/1/15.4号需要4票,给5号方案中得不到6号和8号各1个,就有3票了,再给其它3个人中随便一个人2个,自己得96个.方案是96/0/1/2/1/0/0或96/0/1/0/1/2/0或96/0/1/0/1/0/26.3号需要5票,给5号1 个,再给7号9号10号一人1个(原因同第4点)自己得96个,方案是96/0/1/0/1/0/1/17.2号需要5票,给3号方案中得不到的4号,6号,8号各一个,再给得一个的5,7,9,10中的一个人2个.自己得95个,方案不写了.8.1号需要6票,先给3号一个,再给5,7,9,10一人1个,自己得95个,方案是95/0/1/0/1/0/1/0/1/1

Answer 2

A. 每一个海盗都想由自己来主导分配，因此下一号海盗总是会无条件反对上一个的提案，比如2会反对1、3会反对2等等；

B.每一个海盗都会根据推测他人的策略来决定自己的策略；

然后倒推分析：

1、当剩下9号、10号时，9号会按100/0来分配，因此10号的收益期望值是0。所以，对于10号而言，只要是有人分给他大于0，他肯定会同意；

2、对于8号而言，会想到9号肯定会反对自己的任何方案，因此8号会按99/0/1的方案来分配，争取10号的支持而淘汰9号；所以，对于9号而言，收益期望值也是0。

3、对于7号而言，8号肯定会反对自己，那么7号只要再争取9、10号中的1人同意即可，那么他可以选择给其中1人1块金子即可过关，分配方案是 99/0/0(1)/0(1)。此时，8号的收益期望值也是0。

4、同理，对于7、6、5、4、3、2的任何一位，他们的思考方式和上述的7号、8号是一样的，这样的话，2-7号的收益期望值也是0。

5、综上，2-10号的每一位收益期望值都是0，只要有人给他们分配的大于0他们就会同意。所以对于1号而言，为了争取50%的支持率的话，除掉2号不用考虑，剩下的8个人中只要随意分给4个人各1块金子即可过关。

分配方案就是：1号96块，2号0块，3-10号其中的任意4个人各一块。