| easy | strategy |
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?
Here n=5, think in terms of what happens if n=1,2,3...
Coin distribution is: (98, 0, 1, 0, 1) from levels (5, 4, 3, 2, 1) respectively
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.