海盗分金币

Pirates & The Treasure

专题: Strategy / 策略
难度: L2
来源: Brainstellar

题目详情

五名海盗要分 100 枚金币，海盗有 1~5 的等级，等级 5 最高且是领袖。

领袖提出分配方案，所有海盗（包括领袖）投票：若赞成票不少于一半，则按方案分配；否则，当前最高等级海盗被踢下船，由次一级海盗成为新领袖提出新方案，重复直到方案通过。

所有海盗都极其聪明且极其贪婪（在能活命的前提下，优先最大化自己拿到的金币）。问：等级 5 的海盗应如何分配？

提示：从 $n=1,2,3,4$ 的情况倒推到 $n=5$ 。

Five pirates need to divide 100 Gold Coins. Pirates have a hierarchy, from Level 1 to level 5. The highest level pirate is the leader. The leader proposes a plan to distribute the gold and all the pirates vote on it (including the leader). If at least 50% of the pirates agree on the plan, the gold is split according to the proposal. If not, level-5 pirate is kicked from the ship, and the level-4 pirate now proposes a new plan. This process continues until a proposal is accepted. All pirates are extremely smart and extremely greedy. How does level-5 Pirate divide the treasure?

Hint

Here n=5, think in terms of what happens if n=1,2,3...

解析

分配方案（按等级 5,4,3,2,1 的顺序）为： $(98,0,1,0,1)$ 。

倒推思路：

当只剩 2 人（P2,P1）：P2 只要给自己全拿即可通过（50% 赞成即可），所以 (100,0)。
3 人（P3,P2,P1）：如果否决，P2 会让 P1 得 0，因此 P3 只需用 1 枚金币贿赂 P1 即可通过：(99,0,1)。
4 人（P4,P3,P2,P1）：否决后会进入 3 人局，届时 P2 得 0，因此 P4 用 1 枚金币贿赂 P2 即可：(99,0,1,0)。
5 人（P5,P4,P3,P2,P1）：否决后进入 4 人局，届时 P3 与 P1 得 0，因此 P5 分别给 P3、P1 各 1 枚即可：(98,0,1,0,1)。

这样在保证方案通过的同时，领袖拿到的金币最多。

Original Explanation

Coin distribution is: (98, 0, 1, 0, 1) from levels (5, 4, 3, 2, 1) respectively

Solution

Let the pirates be called P5, P4, P3, P2, P1. P5 is the leader.

Let's study a simpler case with only 2 pirates. P2 can propose to take all the 100 gold coins. Even if P1 votes against this, P2 will vote in favor and the proposal will still be accepted (50% acceptance) leaving P1 with zero coins. The distribution is (100, 0) for levels (2, 1) respectively.

Now let's look at the case with 3 pirates. P3 knows that if this proposal is not accepted, then P2 will get all the gold and P1 will get nothing. So P3 can bribe P1 with one gold coin. P1 knows that one gold coin is better than zero, and hence votes in favor of this proposal. Therefore, P3 can propose the following distribution {Level 3 pirate: 99, Level-2: 0, Level-3: 1}. Since pirate 1 and 3 will vote in favor, this proposal will be accepted. The distribution is (99, 0, 1) for levels (3, 2, 1) respectively.

If there are 4 pirates, P4 can extend this pattern by bribing those who would get nothing in 3-pirates case, to ensure their votes. So the distribution will be (99, 0, 1, 0) for levels (4, 3, 2, 1) respectively, this will ensure that P2 will vote in favor and with the help of self voting (P4), we have 50% votes to accept this proposal.

Similarly, P5 can bribe P3 and P1 pirates because they get nothing if the proposal is rejected, as P4 was giving them nothing. Hence, at level-5, the proposal is (98, 0, 1, 0, 1). This proposal will get accepted and provide the maximum amount of gold to the leader.

This puzzle gives a basic idea of game theory and dynamic programming.