Pirate Gold Division: Extending the Pattern
Consider the classic pirate gold division problem. There are $n$ pirates ranked by seniority (Pirate $n$ is the most senior). They must divide 100 gold coins. The rules are:
- The most senior surviving pirate proposes a division of the coins.
- All pirates (including the proposer) vote. If at least half vote in favor, the proposal passes.
- If the proposal fails, the proposer is thrown overboard, and the next most senior pirate proposes.
- Pirates are perfectly rational, greedy (prefer more gold), and above all else prefer survival.
Work through the optimal proposals for $n = 6$ and $n = 7$ pirates using backward induction from the known cases ($n = 1$ through $5$). Then identify the general pattern: how does the proposer's share and the set of bribed pirates change as $n$ increases?
Finally, what is the maximum number of pirates that can play this game with 100 gold coins such that the most senior pirate still survives?
Hints
- Work backward from the small cases you already know. For each new pirate, ask: who got nothing in the previous round?
- The proposer needs $\lceil n/2 \rceil$ votes total. Since they always vote for themselves, they need to buy $\lceil n/2 \rceil - 1$ votes -- and the cheapest votes come from pirates who would get 0 if the proposer dies.
- Track which pirates receive 0 coins at each stage. You will notice the bribed set alternates between odd-numbered and even-numbered pirates as $n$ increases by 1.
Worked Solution
How to Think About It: This is one of the great backward induction puzzles. The key insight is that every pirate can figure out exactly what happens if they get thrown overboard, so the proposer only needs to offer the cheapest possible bribes to secure a majority. A pirate who would receive 0 coins in the next round will happily vote yes for just 1 coin. The proposer exploits this ruthlessly -- buying the cheapest votes available.
Quick Estimate: The proposer needs $\lceil n/2 \rceil$ votes total (including their own), so they must buy $\lceil n/2 \rceil - 1$ votes at 1 coin each. For $n = 6$, that is 2 bought votes costing 2 coins, leaving 98. For $n = 7$, that is 3 bought votes costing 3 coins, leaving 97. The proposer's share drops by 1 coin for every 2 additional pirates. The bribes eventually consume the whole treasure: at $n = 200$ the proposer must buy 99 votes and keeps just 1 coin, so $n = 200$ is the last crew size at which proposing is still profitable.
Approach: Build up from the base cases using backward induction, tracking who gets 0 at each stage (those are the cheaply bribable voters).
Formal Solution:
Base cases (recap):
- $n = 1$: Pirate 1 takes all 100 coins.
- $n = 2$: Pirate 2 takes all 100 coins (votes for themselves, that is 1 out of 2 = 50%, proposal passes). Pirate 1 gets 0.
- $n = 3$: Pirate 3 needs 2 votes. Pirate 1 got 0 in the $n = 2$ case, so offering Pirate 1 just 1 coin secures their vote. Distribution: Pirate 3 gets 99, Pirate 1 gets 1, Pirate 2 gets 0.
- $n = 4$: Pirate 4 needs 2 votes. Pirate 2 got 0 in the $n = 3$ case. Distribution: Pirate 4 gets 99, Pirate 2 gets 1, Pirates 1 and 3 get 0.
- $n = 5$: Pirate 5 needs 3 votes. Pirates 1 and 3 got 0 in the $n = 4$ case. Distribution: Pirate 5 gets 98, Pirates 1 and 3 each get 1, Pirates 2 and 4 get 0.
$n = 6$:
Pirate 6 needs $\lceil 6/2 \rceil = 3$ votes (including their own), so they must buy 2 votes. In the $n = 5$ case, Pirates 2 and 4 received 0 coins, so they are the cheap votes. Pirate 6 offers them 1 coin each.
Distribution: Pirate 6 gets 98, Pirates 2 and 4 each get 1, Pirates 1, 3, and 5 get 0.
$n = 7$:
Pirate 7 needs $\lceil 7/2 \rceil = 4$ votes, so they must buy 3 votes. In the $n = 6$ case, Pirates 1, 3, and 5 received 0 coins. Pirate 7 offers each of them 1 coin.
Distribution: Pirate 7 gets 97, Pirates 1, 3, and 5 each get 1, Pirates 2, 4, and 6 get 0.
The pattern:
- The proposer (Pirate $n$) keeps $100 - (\lceil n/2 \rceil - 1)$ coins (as long as this is nonnegative).
- They bribe exactly the $\lceil n/2 \rceil - 1$ pirates who received 0 in the $(n-1)$ case, giving each 1 coin.
- The bribed pirates alternate in parity: for even $n$, the proposer bribes even-numbered pirates; for odd $n$, the proposer bribes odd-numbered pirates.
- The proposer's share decreases by 1 coin for every 2 additional pirates.
Maximum number of pirates:
The proposer needs $\lceil n/2 \rceil$ votes (including their own) and must buy $\lceil n/2 \rceil - 1$ of them at 1 coin each, keeping $100 - (\lceil n/2 \rceil - 1)$ coins. Tracking this as $n$ grows:
- At $n = 200$: they need 100 votes, buy 99, and keep $100 - 99 = 1$ coin. This is the largest crew for which the most senior pirate still ends up with any gold.
- At $n = 201$: they need 101 votes, spend all 100 coins on bribes, and keep 0. They still vote for their own proposal (survival beats gold), so it passes 101-to-100 -- they survive but gain nothing.
- At $n = 202$: they need 101 votes = their own + 100 bought. In the 201-pirate case, 101 pirates end up with 0 coins, so buying 100 of them for 1 coin each secures exactly half the votes -- they survive, again with 0 coins.
- At $n = 203$: they need 102 votes but can muster at most their own + 100 bought = 101 -- they are thrown overboard.
- Beyond that, survival becomes sporadic: pirates who are doomed in the continuation vote yes for free, so Pirate 204 survives (Pirate 203's free vote + their own + 100 bribes), then 205--207 die, 208 survives, and in general the proposer survives exactly at crew sizes $n = 200 + 2^k$ (204, 208, 216, 232, ...). Bare survival therefore has no finite maximum.
Answer: $n = 200$ is the largest game in which the most senior pirate still comes out ahead: Pirate 200 bribes 99 pirates with 1 coin each and keeps 1 coin. Past 200 the proposer never profits again -- at $n = 201$ and $n = 202$ they survive with 0 coins, at $n = 203$ they die, and beyond that they survive only at crew sizes $n = 200 + 2^k$, propped up by free votes from doomed pirates. The general pattern (while bribes are affordable): Pirate $n$ keeps $100 - \lceil n/2 \rceil + 1$ coins and bribes $\lceil n/2 \rceil - 1$ alternating-parity pirates with 1 coin each.
Intuition
This puzzle is a masterclass in backward induction and the power of credible threats. Each pirate can perfectly predict the future -- they know exactly what happens if the current proposal fails. The proposer exploits this by identifying the pirates in the worst position (those who get nothing in the next scenario) and buying their votes for the minimum price. It is ruthlessly efficient: you never pay more than you have to, and you never bribe someone who would vote for you anyway.
The deeper lesson for quant work is about understanding outside options. In any negotiation or mechanism design problem, the equilibrium price of someone's cooperation depends on their alternative. Here, a pirate's alternative is what they get if the proposer dies -- and if that alternative is 0, their vote costs just 1 coin. This same logic appears in auction theory (bidding just above the second-highest valuation), options pricing (the value of exercising versus holding), and compensation negotiations. The pattern also has a surprising endgame: with only 100 coins, the proposer profits up to $n = 200$ (keeping a single coin). At 201 and 202 pirates the most senior pirate survives with nothing, at 203 he is thrown overboard, and beyond that he survives only at crew sizes $200 + 2^k$ -- kept alive by doomed pirates who vote yes for free, because survival is worth more than gold.