Five pirates are figuring out how to divide up a newly plundered treasure of 100 gold coins. From most senior to least senior: Pirate A, Pirate B, Pirate C, Pirate D, and Pirate E. The rules:
- The most senior pirate must propose a distribution (for example, giving himself all 100 gold coins and 0 for everyone else), and then all the pirates must vote on it.
- If at least half of the pirates vote for a proposal, the proposal is accepted and the gold is split according to that distribution.
- Otherwise, if the proposal is rejected, the pirate that proposed it is kicked out, and this process repeats with the remaining pirates.
- Each pirate’s main goal is to maximize the gold they receive (but a pirate that is kicked out gets no gold), but are also spiteful enough to prefer kicking out the other pirates, all else equal. The pirates are also distrustful of each other and will not make any side deals, so the distribution of an accepted proposal is final.
What is the greatest number of coins that Pirate A can distribute to himself?
This is a classic logic puzzle, occasionally encountered in tech interviews many years ago.
Preparing for a brain teaser interview? Check out our ultimate guide to brain teaser interviews.
Solution
Pirate A can get 98 of the coins by distributing just 1 coin to Pirate C and 1 to Pirate E!
The easiest way to deduce this is to work backwards:
- If only D and E remain, D can give himself all 100 coins because his own vote is enough to accept his proposal.
Distribution: (0, 0, 0, 100, 0) - If only C, D, and E remain, C needs 2 votes including his own. C knows he can win E’s vote by giving him 1 coin, because they all know E would get 0 coins if C’s proposal was rejected and D got to make a proposal (see above).
Distribution: (0, 0, 99, 0, 1) - If B, C, D, and E remain, B needs 2 votes including his own. B knows he can win D’s vote by giving him 1 coin, because they all know D would get 0 coins if B’s proposal was rejected and C got to make a proposal (see above).
Distribution: (0, 99, 0, 1, 0) - Since they all know that C and E will get 0 coins if B makes a proposal, A can convince C and E to vote for his proposal by giving them each just 1 coin!
Distribution: (98, 0, 1, 0, 1)