发新话题
打印

海盗分宝石

海盗分宝石

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

[ 本帖最后由 零点守候 于 2008-6-14 18:00 编辑 ]

TOP

谁知道这题怎么思维的,说说看啊

TOP

这是网上的一道题,上面的答案是两种都没过程,第一种是:97   0    1     2     0第二种是:97   0    1     0      2       相传这道题在美国能在20分钟内解决的话,年薪都在8万美金以上,我倒没想得那8万美金,只不过想看看自己到底和8万美金相差多远。呵呵

本人想了几天,今天想出了1个分配方案还和他们的不一样,说出来和大家讨论一下是否确,
就是一号98   二号0   三号1   四号0     五号1

我用的是反向证明方法:
假如前面的人都被处决了,就剩下两人,4号和5号, 那么4号100    5号为0
这样5号就不会让3号轻易的处决,

假如就剩下三人3号、4号和5号    3号要想自己的利益大考虑到5号的处境,分配方案应是
3号99    4号0    5号1   这样4号就得不到利益,4号就不会让2号轻易的处决,

假如就剩下四人2号、3号、4号和5号    2号要想自己利益最大又能通过就要考虑到4号的处境,分配方案应是2号99    3号0    4号1   5号0   那么3号和5号就不会让1号轻易处决,

5人分配,1号要想使自己利益最大,必须有2人支持自己,
2号是满足不了他的,所以不能让他支持自己,2号也只能分0颗了,
根据2号的分配方案,3号可以是支持者条件是收益必须大于2号的分配方案,所以3号分1颗,
现在再找一人支持自己就可以了,要么4号要么是5号
同样4号,在2号的分配中他得过1颗,要想拉扰他就要大于1所以给他2颗,可5号在2号的分配中是0要他支持1颗就行
所以98       0        1         0          1

TOP

回复 3# 的帖子

当且仅当超过半数的人同意时,按照他的方案进行分配,否则将被扔入大海喂鲨鱼
是否改成:至少半数的人同意时,---------        
假设只剩下偶数个人进行分配时,5号就会思考前面的号数与自己的利益关系。否则,只剩下最后两个人时,如何分配?
 
淌过夏夜童年的血液 张扬红色的青春 轻狂在流逝的冬日 潺潺的记忆觅不到尽头

TOP

我在网上搜到这个题的答案,正好粘过来楼主看下可以做个参考。
用倒推法:

假设只剩下4、5号,那么四号无论怎么分,5号都会反对,就算是四号把100颗都给5号,5号还是反对,因为5号心里很清楚:只要自己反对,票数不过半,那么四号必死。那么100颗宝石都是自己的。这样四号也死了,自己还得到了100颗宝石。所以这种情况下是  4号(死),5号 (100颗)。

假设只剩下3、4、5号。那么无论3号怎么分,就算是100  0   0 ,四号都会赞成(为了保命,宁愿不要宝石),当然3号一定会赞成自己的分法。这样3个人中至少2个人赞成,超过半数。所以3号最希望剩下他们三个人。这种情况下是  3号 (100颗),4号(0颗,虽然没有宝石,但是保住了姓名),5号(0颗),

假设只剩下2、3、4、5号。3号一定反对,但是2号只要给4、5号任意一颗,他俩都会赞成,这种情况下是2号(98颗),3号(0颗),4号(1颗),5号(1颗)。

假设1、2、3、4、5号都在,1号很清楚,只要再争取到2个人的赞成,这样5个人中,就有3个人赞成了,超过半数,可以分配。这个时候1号会怎么分呢?他只要比2号分的多一点就可以了。即给三号1颗,然后4号或者5号其中一个人给2颗。
所以宝石的分配方案是1号(97颗),2号(0颗),3号(1颗),4号(2颗),五号(0颗)或者
                                              1号(97颗),2号(0颗),3号(1颗),4号(0颗),五号(2颗).

[ 本帖最后由 张济2681 于 2008-8-8 10:24 编辑 ]
此人很懒,什么也没有留下……

TOP

楼主可能有一点理解错误了。这句话“当且仅当超过半数的人同意时,按照他的方案进行分配“
就是超过半数才可以,正好等于半数,还是不行。
此人很懒,什么也没有留下……

TOP

回复 6# 的帖子

是理解错了,看了你的分析很清楚了,谢谢!
帮助别人;提高自己!

TOP

发新话题