Pirate Game and Coupon Collector's Problem
Solve these two classic brain teasers:
(a) The Pirate Game: Five pirates (ranked 1 through 5 by seniority, with 5 being the most senior) must divide 100 gold coins. The most senior pirate proposes a split. All pirates vote, and the proposal passes if at least half vote in favor (the proposer can vote for himself). If it fails, the proposer is thrown overboard and the next most senior pirate proposes. Each pirate is perfectly rational, wants to maximize gold, and prefers survival above all else. What split does Pirate 5 propose?
(b) The Coupon Collector: There are $n$ distinct coupon types. Each time you buy a product, you receive one coupon uniformly at random. What is the expected number of purchases needed to collect all $n$ types?
Hints
- For the pirate game, start from the base case of 2 pirates and work forward. At each stage, the proposer only needs to buy the cheapest available votes.
- For the coupon collector, break the process into phases: phase $k$ is the wait for the $k$-th new coupon. Each phase is a geometric random variable.
- The coupon collector's expected time is $n \sum_{j=1}^n 1/j = n H_n$ by linearity of expectation over the geometric phases.
Worked Solution
How to Think About It: These are two very different problems bundled together. The pirate game is pure backward induction -- you start from the simplest case (2 pirates) and work forward. The coupon collector is a linearity-of-expectation problem -- break the collection process into phases and compute each phase's expected duration separately.
Part (a): The Pirate Game
Quick Estimate: Pirate 5 needs 3 votes (out of 5, including his own). He can buy 2 votes cheaply by offering those pirates slightly more than they would get if he were eliminated. The key is figuring out what each pirate gets in the "next" scenario.
Backward induction:
2 pirates (Pirate 2 proposes): Pirate 2 needs 1 vote (himself). He takes everything. - Split: Pirate 1 gets 0, Pirate 2 gets 100.
3 pirates (Pirate 3 proposes): Pirate 3 needs 2 votes. He votes for himself. Pirate 1 would get 0 if Pirate 3 is eliminated, so offering Pirate 1 just 1 coin buys his vote. - Split: (1, 0, 99).
4 pirates (Pirate 4 proposes): Pirate 4 needs 2 votes. He votes for himself. If Pirate 4 is eliminated, the 3-pirate split is (1, 0, 99). Pirate 2 gets 0 in that scenario, so offering Pirate 2 just 1 coin buys his vote. - Split: (0, 1, 0, 99).
5 pirates (Pirate 5 proposes): Pirate 5 needs 3 votes. He votes for himself. If Pirate 5 is eliminated, the 4-pirate split is (0, 1, 0, 99). Pirates 1 and 3 each get 0 in that scenario, so offering each of them 1 coin buys their votes. - Split: (1, 0, 1, 0, 98).
Pirate 5 proposes: Pirate 1 gets 1, Pirate 2 gets 0, Pirate 3 gets 1, Pirate 4 gets 0, Pirate 5 keeps 98. This passes 3-2.
Part (b): The Coupon Collector
Quick Estimate: For $n = 10$: the answer is $10 \cdot H_{10} = 10(1 + 1/2 + \cdots + 1/10) \approx 10 \times 2.93 = 29.3$. It takes about 3 times as many purchases as there are coupon types. For large $n$, $E[T] \approx n \ln n + \gamma n \approx n \ln n + 0.577n$.
Formal Solution:
Divide the collection process into $n$ phases. Phase $k$ starts when you have exactly $k - 1$ distinct types and ends when you get the $k$-th new type.
During phase $k$, each purchase gives a new type with probability $(n - k + 1)/n$. The number of purchases in phase $k$ is geometric with success probability $(n - k + 1)/n$, so the expected duration is:
$$E[T_k] = \frac{n}{n - k + 1}$$
By linearity of expectation, the total expected number of purchases is:
$$E[T] = \sum_{k=1}^{n} E[T_k] = \sum_{k=1}^{n} \frac{n}{n - k + 1} = n \sum_{j=1}^{n} \frac{1}{j} = n \cdot H_n$$
where $H_n = 1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n}$ is the $n$-th harmonic number.
Using the asymptotic expansion of the harmonic series:
$$E[T] = n\left(\ln n + \gamma + \frac{1}{2n} + O(n^{-2})\right)$$
where $\gamma \approx 0.5772$ is the Euler-Mascheroni constant.
Answer:
(a) Pirate 5 proposes the split (1, 0, 1, 0, 98), which passes 3-2 with Pirates 1, 3, and 5 voting yes.
(b) The expected number of purchases is $E[T] = n H_n = n(\ln n + \gamma + O(1/n))$, where $H_n$ is the $n$-th harmonic number.
Intuition
The pirate game illustrates the power of backward induction in game theory. The counterintuitive result -- that the most powerful pirate keeps almost everything -- comes from the fact that in each sub-game, some pirates are completely expendable and can be bought for just 1 coin. The proposer exploits this ruthlessly. In market design and auction theory, similar backward-induction reasoning determines equilibrium strategies.
The coupon collector's problem is a masterclass in linearity of expectation. Instead of analyzing the complicated random process directly, you decompose it into independent geometric phases. The harmonic series $H_n \approx \ln n$ means the last few coupons are disproportionately expensive to collect -- the last coupon alone takes $n$ expected purchases. This "long tail" phenomenon appears everywhere: in data deduplication, in testing coverage, and in the difficulty of reaching 100% of any target when progress is random.