Question

海盗来了最多能偷多少金币

Answer 1

这个问题可以利用递归推理来解决.n个海盗的问题可以通过对n-1个海盗的状况进行分析得到解决.一直这样进行,我们可以先考虑只有一个海盗的情况.
很明显,如果只有1个海盗活下来,那么他1个人就可以独得100块金币.如果有2个海盗会是什么情况呢?2个海盗中资格较老的一位要首先提出分配建议.问题中规定只要半数通过就有效,也就是说资格较老的海盗自己投一张赞成票就可以使提议通过.因此,他丝毫不用顾虑另外一个海盗的想法和感受.要知道他是一个贪婪的海盗,他会独吞这100块金币,投票的结果是1比1,提议生效.
我们继续分析有3个海盗的情况.把3个海盗按照资格从新到老编为1号,2号,3号.那么就应该由3号海盗来首先提出分配方案.如果3号海盗提出的方案是自己独吞100块金币而剩下两人分文没有,2号海盗肯定会反对这个方案,因为他知道,如果3号海盗被消灭掉,只剩下2个人之后,自己就可以得到所有的金币了,1号海盗是一个摇摆不定的投票者:在3号海盗的方案下他一无所获,而只有2个海盗时他依旧一无所获.他没有理由为哪一方投赞成票.
因此如果3号海盗足够聪明的话,他就会收买1号海盗的选票.他给1号海盗的金币不会比应付的多出一个子儿. 他的分配方案是给1号海盗1块金币,给2号海盗0块金币,剩下的99块金币就归3号海盗所有.1号海盗知道,如果3号海盗的方案没有通过而被杀死,自己肯定是分文不得,现在虽然只能得到1块金币,但总是聊胜于无,因此会投3号海盗的赞成票.这样的投票结果是2比1,方案获得通过.
现在我们来看看有4个海盗时的情况,4是一个偶数,因此资格最老的海盗除了自己的一票,如果还能争取到一张选票,他的方案就可以获得通过.他所面临的问题是,购买其他3个海盗中哪一个人的选票最划算呢?
回过头在看看3个海盗时的情况,如果只有3个海盗,2号海盗肯定就会一无所获.因此,4号海盗的方案就是购买2号海盗的选票.
只要有了2号选票的选票在手,4号海盗就不用担心3号海盗和1号海盗的想法了.4号海盗会给1号海盗0块金币,2号海盗1块金币,3号海盗0块金币,而自己独拿99块金币.
现在我们看到了问题的实质,在每一个例子中,资格最老的海盗都必须“购买”自己需要的选票,并要以尽可能低的价格,然后剩余的金币都归自己.
现在我们来看看5个海盗时的情景,也就是我们要解决的这个问题.你是5号海盗,你需要3张选票,1张你自己的,2张别人的.因此你需要给4个海盗中的2个海盗一点好处,应该是1号和3号.因为如果你(5号海盗)被杀的话,他们2个将会一无所获.只要你 “给他们点东西”,他们就会投你的赞成票.因此,你的方案应该是给4号海盗0块金币,3号海盗1块金币,2号海盗0块金币,1号海盗1块金币.剩下的98块金币就归你了.