【IT笔试面试题整理】海盗分宝石

【试题描述】

5个海盗抢到了100颗宝石,每一颗都一样的大小和价值连城。

他们决定这么分:

1.抽签决定自己的号码(1,2,3,4,5)

2.首先,由1号提出分配方案,然后大家5人进行表决,当且仅当超过半数的人同意时,按照他的提案进行分配,否则将被扔入大海喂鲨鱼

3.如果1号死后,再由2号提出分配方案,然后大家4人进行表决,当且仅当超过半数的人同意时,按照他的提案进行分配,否则将被扔入大海喂鲨鱼

4.以次类推

条件:

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

问题:

第一个海盗提出怎样的分配方案才能够使自己的收益最大化?

【试题分析】

首先,看4、5号.如果仅仅剩下这两人。4号肯定选100:0,因为即使5号不同意,按照规则,4号自己同意自己的提案,也算达到半数。所以,5号肯定不会等到4号来表决,他必须支持前三个提案中,给自己最多的一个提案,因为到了4号提案的时候,他肯定什么也得不到。可以推导到3号,如果3号选择给自己99个,4号0个,5号1个,那么5号就不得不同意了,因为这样他至少能得到一个,比最后由4号提案,他什么都得不到强。也就是说,轮到3号提案,他肯定是99:0:1。

也就是说,如果轮到3号选择,4号什么都得不到,那么4号肯定要在前二个提案里,选择一个给自己最多的提案。这时,2号只要在3、4、5号中,赢得一个支持者,就足够获得最终胜利。2号的提案可以是98:0:1:1或98:0:2:0。分析前者,5号在3号那里也可以得到这么多钻石,4号就没得选择,他必须同意2号得提案,否则3号提案时,他什么也分不到;后提案就是针对4号,虽然4号没机会选择,但如果给予他意外的惊喜,他会更加支持2号提案,可以使2号的此提案100%通过。其实这两种提案,本质上没有差别。

不难看出,3号在2号的两种提案里,都不会有好处,也就是说,3号只要能在1号提案中得到好处,就会支持1号的提案。于是,1号的提案里,要充分给予3号的利益,2号的完全可以可以忽略,因为无论如何,2号都不会同意1号的分配方案。

现在,3号只要能获得1个或者1个以上的钻石,4号只要获得2个或2个以上的钻石,5号只要获得1个或1个以上的钻石,就会支持1号提案。实际情况下,如果3、4号都同意,提案不需要5号同意照样可以

【参考答案】

1号自己利益最大化和确保提案通过的分配方法:

1号97个;2号0个;3号1个;4号2个;5号0个