Five pirates and a hundred coins
Five pirates, ranked A (most senior), B, C, D, E, must share 100 gold coins, which cannot be cut. The most senior pirate still aboard proposes a split, and every pirate still aboard votes on it, the proposer included.
- If at least half of the votes are yes, the coins are shared as proposed.
- Otherwise the proposer is thrown overboard and the next most senior pirate makes a proposal under the same rules.
Every pirate is perfectly rational and wants first to stay alive, then to get as many coins as possible. When two outcomes give him the same number of coins, he prefers the one where a pirate is thrown overboard. So a pirate votes yes only if the proposal gives him strictly more than he would get if it were rejected.
How many coins does A keep?
Fractions, decimals with at least 3 significant digits, and expressions such as sqrt(2)/2, e^-1 or pi/4.
Start from the end. What happens when only D and E are left?
With three pirates left, C needs one vote besides his own. Which pirate is cheapest to buy, and what does he cost?
h
s Shown after a correct answer. Revealing it first marks the problem as seen, not solved.
Idea. Solve the game backwards. With pirates left, the proposer knows exactly what each of the others would get if he were thrown overboard, so he buys the votes he needs from the pirates who would get the least, paying each one coin more than that.
Two pirates (D, E). D's own vote is half of the votes, so any proposal of his passes. He keeps everything: D gets 100, E gets 0.
Three pirates (C, D, E). C needs 2 votes out of 3: his own and one more. E would get 0 if C were thrown overboard, so 1 coin buys E's vote. The split is C 99, D 0, E 1.
Four pirates (B, C, D, E). B needs 2 votes out of 4. D would get 0 in the three-pirate game, so 1 coin buys him. The split is B 99, C 0, D 1, E 0.
Five pirates. A needs 3 votes out of 5: his own and two more. In the four-pirate game C and E get 0, so each can be bought for 1 coin. (D gets 1 there and would cost 2.) The split is
So A keeps 98 coins.
The rules matter. The answer depends on the voting rule and on the tie-break. If a strict majority were needed, or if a pirate who is offered exactly what he would get otherwise voted yes, the backward induction would change. Some write-ups give the split as 98, 0, 1, 2, 0; under these rules that overpays D, who would accept 1 coin, but it does not change A's 98.