海盗战利品

Pirate Loot

专题: Brainteaser / 脑筋急转弯
难度: L2
来源: OpenQuant

题目详情

5 名海盗从热带岛屿抢劫了 100 枚硬币。他们必须投票决定如何分配这些硬币。投票流程如下：

最年长的海盗提议分割（例如：20、20、20、20、20）
如果最年长的海盗的计划获得至少 50% 的批准（他可以投票给自己），则该计划通过。否则他就会被处决，并且对下一个最年长的海盗重复这个过程。

该过程将持续到计划获得批准为止。最年长的海盗会得到多少金币？

假设如下：

所有海盗都是完全理性的，并把生存放在第一位
在活着之后，所有海盗都寻求最大化收入

5 pirates have looted 100 coins from a tropical island. They must vote on how to divide these coins amongst each other. The voting process is as follows:

The oldest pirate proposes a split (ex: 20, 20, 20, 20, 20)
If the oldest pirate's plan gets at least 50% approval (he can vote for himself), the plan is passed. Otherwise he is executed and the process repeats itself with the next oldest pirate.

The process will continue until a plan is approved. How many gold coins will the oldest pirate get?

Assume the following:

All pirates are perfectly rational and place the highest priority on staying alive
After staying alive, all pirates seek to maximize earnings

解析

这个问题可以通过递归的方式思考来解决。我们首先考虑基本情况，然后构建 5 个海盗的问题描述。

如果有 1 个海盗 ( $n=1$ )，他将获得全部 100 个金币。

如果有 2 个海盗 ( $n=2$ )，最年长的海盗（表示为海盗 #2）将提出分割方案，其中他获得 100 个硬币，另一个海盗（海盗 #1）获得 0 个硬币。这种分裂是保证通过的，因为只有 50% 的海盗必须批准该提案，并且最年长的海盗将批准它。

如果有 3 个海盗 ( $n=3$ )，最年长的海盗（海盗 #3）将提出分割方案，其中他保留 99 个硬币，并将 1 个硬币交给海盗 #1。海盗 #1 被激励去批准该计划，因为如果他拒绝该计划，他认识到他将回到 $n=2$ 的情况，在这种情况下他没有得到任何硬币。

如果有 4 个海盗（ $n=4$ ），最年长的海盗（海盗 #4）给自己 99 个硬币，并给海盗 #2 1 个硬币。海盗 #2 会被激励批准该计划，因为如果他拒绝该计划，他就会意识到他将回到 $n=3$ 的情况，在这种情况下他不会得到任何硬币。

最后，如果有 5 个海盗 ( $n=5$ )，最年长的海盗（海盗 #5）会给自己 98 个硬币，并给海盗 #3 1 个硬币和给海盗 #1 1 个硬币。如果这些海盗不投票批准该计划，他们将一无所获。

因此这个问题的答案是 $\boxed{98}$ 。你可能已经观察到此问题中出现了一种模式。在每一步中，最年长的海盗都会选择向上一步中没有获得金币的海盗提供金币（直到他获得 $n/2$ 选票）。

Original Explanation

This problem can be solved by thinking about it recursively. Let's first consider the base case and then build up to the problem description with 5 pirates.

If there is 1 pirate ( $n=1$ ) he will get all 100 coins.

If there are 2 pirates ( $n=2$ ) the oldest pirate (denoted as pirate #2) will propose a split in which he gets 100 coins and the other pirate (pirate #1) gets 0 coins. This split is guaranteed to pass because only 50% of the pirates must approve the proposal and the oldest pirate will approve it.

If there are 3 pirates ( $n=3$ ) the oldest pirate (pirate #3) will propose a split in which he keeps 99 coins and gives 1 coin to the pirate #1. Pirate #1 is incentivized to approve the plan because if he rejects the plan he recognizes that he will be back to the case where $n=2$ in which he gets no coins.

If there are 4 pirates ( $n=4$ ) the oldest pirate (pirate #4) gives himself 99 coins and gives 1 coin to pirate #2. Pirate #2 is incentivize to approve the plan because if he rejects the plan he recognizes that he will be back to the case where $n=3$ in which he gets no coins.

Lastly, if there are 5 pirates ( $n=5$ ) the oldest pirate (pirate #5) gives himself 98 coins and gives 1 coin to pirate #3 and 1 coin to pirate #1. Each of these pirates will get nothing if they do not vote to approve the plan.

Therefore the answer to this problem is $\boxed{98}$ . You may have observed that a pattern emerges in this problem. In each step, the oldest pirate will choose to give coins to the pirates who get no coins in the previous step (until he secures $n/2$ votes).