Tuesday, July 10, 2007

我面试时的题目 ~好难!~

5个海盗分钻石
这是一个有趣的“智力游戏题”:

5个海盗抢到了100颗质地完全一样的钻石,但又不愿意平分,最后5个人同意抓阄解决:按照1,2,3,4,5的抓阄结果,将5个人编号。抓到1的是1号,抓到2的是2号,依次类推。现由抓到“1”的1号海盗提出分配方案,为了防止他分配不公,海盗们达成一致:他的方案必须有所有人(包括1号自己)的半数以上(注意,必须大于50%)通过才可执行。否则,他将被杀死,再由2号海盗提出分配方案,2号的方案也要所有剩下的人(包括他自己)的半数以上通过。否则他也将被杀死,依次类推。假设这5个海盗都贪婪成性、残忍无比、绝顶聪明而又一诺千金,都想自己得到最多,都想看到别人死去而自己活。请问,1号要怎样分配才能使自己得到的钻石最多?

解答:

要回答这个问题,一般人肯定会想到,1号必须先让另外两个人同意,所以,他可以自己得到32颗,而给2号3号各34颗。但只要仔细想想,就会发现不可能,
2号和3号有积极性让1号死,以便自己得到更多。所以,1号无奈之下,可能只有自己得0,而给2和3各50颗。但事实证明,这种做法依然不可行。为什么呢?

因为我们要先看4号和5号的反应才行。很显然,如果最后只剩下4和5,这无论4提出怎样的方案,5号都会坚决反对。即使4号提出自己要0,而把100颗钻石都给5,5也不会答应――因为5号愿意看到4号死掉。这样,5号最后顺利得到100颗钻石——因此,4的方案绝对无法获得半数以上通过,如果轮到4号分配,4号只有死,只有死!

由此可见,4号绝对不会允许自己来分。他注定是一个弱者中的弱者,他必须同意3号的任何方案!或者1号2号的合理方案。可见,如果1号2号死掉了,轮到3号分,3号可以说:我自己100颗,4号5号0颗,同意的请举手!这时候,4号为了不死,只好举手,而5号暴跳如雷地反对,但是没有用。因为3个人里面有2个人同意啊,通过率66.7%,大于50%!

由此可见,当轮到3号分配的时候,他自己100颗,4和5都是0。因此,4和5不会允许轮到3来分。如果2号能够给4和5一些利益,他们是会同意的。
比如2的分配方案是:98,0,1,1,那么,3的反对无效。4和5都能得到1,比3号来分配的时候只能得到0要好得多,所以他们不得不同意。
由此看来,2号的最大利益是98。1号要收买2号,是不可能的。在这种情况下,1号可以给4号和5号每人2颗,自己收买他们。这样,2号和3号反对是无效的。因此,1号的一种分配方案是:96,0,0,2,2。

这是不是最佳方案呢?再想一想,1号也可以不给4号和5号各2个,而只需要1个就搞定了3号,因为如果轮到2号来分配,2号是可以不给3号的,3号的得益只有0。所以,能得到1个,3号也该很满意了。所以,最后的解应该是:97,0,1,2,0。

好,再倒推。假设1号提出了97,0,1,0,2的方案,1号自己赞成。2和4反对。3∶2,关键就在于3号和5号会不会反对。假设3号反对,杀掉1号,2号来分配,3自己只能得到0。显然,3号不划算,他不会反对。如果5号反对,轮到2号、3号、4号来分配,5号自己最多只能得到1。

所以,3号和5号与其各得到0和1,还不如现在的1和2。

正确的答案应该是:
1号分配,依次是:97,0,1,0,2;
或者是:97,0,1,2,0。

No comments:

Post a Comment