聚合国内IT技术精华文章,分享IT技术精华,帮助IT从业人士成长

海盗分宝石面试题的头脑风暴

2012-05-14 18:00 浏览: 2238786 次 我要评论(0 条) 字号:


有个面试题,是这样的:

五个海盗得到100颗钻石,颗颗价值连城。这五个海盗非常聪明,都想自己得到钻石最多。因而他们设计了个规则,根据抽签后的顺序, 每个人提出个分配方案,如果有半数以上(不包括半数)的人表决通过,则按这个方案执行,否则提出方案的人要被扔到海里喂鱼。下一个人开始提方案,以此类推。

问:如果你是抽到第一个提方案的人,你该提出什么样的钻石分配方案保住你的小命,并且自己获得钻石尽可能得多?

这类博弈论的问题不能采用一般的常识去做,比如均分的方案根本不可行,大家如果把你否决,剩余的人可以均分得更多呢。这里可以使用逆推的方案。

假设按抽签的顺序, 要提方案的人依次为1, 2, 3, 4, 5。

如果只剩下4和5, 除非把宝石全给5, 否则5肯定不会同意, 这样4的提议就不能通过, 就面临喂鱼的结果。因此4绝对不允许自己来分配宝石。

接着,如果有3,4和5,5必然不会同意,因为主要把3干掉,剩下的宝石其实就是他的了。这里主要争取4的支持,如果能给他一颗,也不错了,所以当3提议的时候,最好的分配方案是——3: 99, 4: 1, 5: 0.

依次类推,如果有2, 3, 4, 5呢?3肯定不会同意了,所以要争取剩下的两个人。可以给4两颗, 给5一颗, 这样对它们来说已经比3的方案多了,还是会投赞成票的。分配方案: 2: 97, 3: 0, 4: 2, 5: 1。

最后到1了,2是不会投赞成票的,所以主要是取得3,4,5其中的两个人的支持就可以了。这时候可以给3一颗,给5两颗,这样对他们两个来说,已经比2的方案好了,他们肯定投赞成票。

因而对一来说,最好的分配方案是—— 1: 97, 2: 0, 3: 1, 4: 0, 5:2。



网友评论已有0条评论, 我也要评论

发表评论

*

* (保密)

Ctrl+Enter 快捷回复