微软经典面试题--海盗分宝石

[CanChn]

5个海盗抢到了100颗宝石，每一颗都一样的大小和价值连城；他们决定这么分：

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

　　2. 首先，由1号提出分配方案，然后大家5人进行表决，当且仅当半数和超过

　　半数的人同意时，按照他的提案进行分配，否则将被扔入大海喂鲨鱼。

　　3. 如果1号死后，再由2号提出分配方案，然后大家4人进行表决，当且仅当

　　半数和超过半数的人同意时，按照他的提案进行分配，否则将被扔入大海喂鲨鱼。

　　4. 以次类推......

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

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

 

[CanChn]

是这样分的

初一看:最后的两人,除非内斗,不然他们是不会有被扔下海的可能,他们两人是最大利益获得者,他们可以通过不断地否决其他人的提议得到所有的钻石.1号要想利益最大化,就只有保住自己的性命,放弃钻石.这样,1号的提议不违背4号5号的利益,才有可能获得他们的支持.那就是1号0颗,2号0颗,3号0颗,4号50颗,5号50颗.

　　但是,2号可以通过否决1号,然后取得另外3人中的任何一个人的支持使自己的提议获得通过与那个人平分100颗.即2号可以得到50颗.3,4,5号都有得到50颗的可能,其中以3号的可能性最小.(由2号提议的话,3号得到50颗的可能性是1/3.

　　在这种情况下,1号可以取得2号,3号的支持,使自己的提议获得通过:

　　1号25颗,2号50颗,3号25颗,4号0颗,5号0颗.

---------------------------------------------------------------------------
Do you have any other answer?

 

[S.H.]

据说　答案是９７　２　１　０　０

 

[AmazingGrace]

哇

 

[难波万]

1号97颗,2号0颗,3号0颗,4号1颗,5号2颗

 

[大漠张三]

是吗？

我觉得：

不给2，因为2肯定会vote no。

给3一颗，因为如果1死了，2肯定不会给他东西的。

给4一颗，因为如果1死了，2可以选择给他一颗或者给5一颗，所以他有可能什么都得不到

给5一颗，我觉得这个很重要，如果不给5，5肯定会vote no, 这样就等于把自己的命交到了4手上，4万一想screw 1 up，那1就死定了

 

[*Nana*低调着疯狂]

那样的话三号岂不是也会反对一号的决定么，因为三号会觉得自己的比二号的少了呀~

这题目不怎么make sense呀。。。至少对我是这样~

 

[镇加东]

楼上的
1只要给3一颗3就不会反对1
因为如果1下了,2是不会给3的,因为3可能推了2再拉4,5中的一个.
所以对1来说
3这一颗必给,给了这一票就稳了
对于剩下的吗,我觉得再给5一颗就够了,对于5来说,当1死了后,2只会给4不会给5,因为5不会死,3也可以拉5的票,5至少可以从3那里拿一颗,
但4很有可能什么都没有,2给4一颗就足够了.
所以我觉得应该是
98,0,1,0,1

 

[紫苑]

反正大家都想人越少越好在只剩下３个人以前是不会考虑让谁通过的，我觉得我会说我跟２一人３３个，３给他３４个，４．５给０个～

 

[大漠张三]

最初由 Fourseasons 发布
反正大家都想人越少越好在只剩下３个人以前是不会考虑让谁通过的，我觉得我会说哪２位先通过我的提议就平均分给他们宝石这样随便２，３会给我通过～．～就每人３３个啦，４，５给０个．．．．．．．．

2是不会同意33个的，把你喂鲨鱼以后他能得到99个

 

[镇加东]

如果我是2,我还会否你
因为我想拿得更多....
嘿嘿

 

[镇加东]

最初由 大漠张三 发布



2是不会同意33个的，把你喂鲨鱼以后他能得到99个

 

[难波万]

5号在1,2,3任何一人提出方案的时候都可以得到1颗~~总感觉给他2颗安全些~~不然他一发神经~~1号就喂鲨鱼了~~4号在1死后1颗都得不到~~所以1号拿他票就够了~~其他的么~~都有2票了~~who give a damn~~

 

[紫苑]

的确很绞人的问题＠＠

 

[难波万]

最初由 难波万 发布
5号在1,2,3任何一人提出方案的时候都可以得到1颗~~总感觉给他2颗安全些~~不然他一发神经~~1号就喂鲨鱼了~~4号在1死后1颗都得不到~~所以1号拿他票就够了~~其他的么~~都有2票了~~who give a damn~~

这是我昨晚想的~~现在想想98 0 0 1 1很安全~~