Can You Solve The Puzzle Of The Pirate Booty?

Ten perfectly rational pirate logicians, ranked from the captain on down, must split ten indivisible gold pieces. The captain proposes a division and everyone, captain included, votes. If at least half vote yes, it passes; otherwise the captain is thrown overboard, the next in rank becomes captain, and the process repeats. Each pirate votes by these rules, earlier ones overriding later: self-preservation (value your life above all), then greed (grab as much gold as possible), then bloodthirst (all else equal, vote to throw someone overboard). How is the gold divided? Extra credit: solve it for $P$ pirates and $G$ gold pieces.

The Riddler, FiveThirtyEight (Kyle Joecken)(original post)

Solution

No one walks the plank. The captain takes six and tosses a single coin to every second pirate beneath him: $$\boxed{6,\,0,\,1,\,0,\,1,\,0,\,1,\,0,\,1,\,0}.$$ The one idea is that a pirate’s vote is bought not with generosity but with the threat of what he gets if the captain dies, so you must know the smaller games before you can price the larger one. Reason from the bottom up, naming the pirates $P_1$ (captain) down to $P_{10}$.

Two pirates left. $P_9$ votes for his own plan, that is one of the two votes, which is at least half, so it passes. He keeps all ten and $P_{10}$ gets nothing.

Three. $P_8$ needs one more vote. $P_{10}$ faces nothing if $P_8$ dies, so a single coin wins him over. $P_8$ keeps nine, $P_9$ nothing, $P_{10}$ one.

Four. $P_7$ needs one extra vote and buys the cheapest pirate who would otherwise get zero, namely $P_9$, for one coin.

The pattern is now fixed. A captain facing $m$ pirates needs $\lceil m/2\rceil$ votes: himself plus $\lceil m/2\rceil-1$ others. He buys exactly those pirates who would receive nothing if he were thrown overboard, one coin each, which is always a coin less than they’d lose. With all ten aboard, $P_1$ needs five votes, so he buys four: $P_3,P_5,P_7,P_9$, the pirates left empty-handed in the nine-pirate game, for one coin apiece, and keeps the remaining six. Bloodthirst never bites because no pirate is ever left indifferent: each bribed pirate is strictly better off voting yes.

Extra credit. As long as the gold covers the bribes, that is $G\ge\lceil P/2\rceil-1$, the same alternating pattern holds: the captain pays one coin to every second pirate down the chain and keeps $G-\bigl(\lceil P/2\rceil-1\bigr)$ for himself (possibly zero, but he keeps his life). Only when the gold runs short of the bribes the captain needs does blood finally get spilled.

The computation

Encode the backward induction. Knowing the division among $m-1$ pirates, the captain of $m$ buys the cheapest votes, one coin more than each target would get without him, until he has enough, and keeps the rest.

def divide(P, G):
    res = {1: [G]}                              # one pirate keeps everything
    for m in range(2, P + 1):
        fallback = res[m - 1]          # what pirates 2..m get if captain dies
        need = (m + 1) // 2            # votes required (>= half, incl. captain)
        alloc, spent = [0] * m, 0
        # cheapest voters first: those who'd get least if the captain is thrown over
        for j in sorted(range(1, m), key=lambda k: fallback[k - 1])[:need - 1]:
            alloc[j] = fallback[j - 1] + 1     # one coin beats their fallback
            spent += alloc[j]
        alloc[0] = G - spent                     # captain keeps the rest
        res[m] = alloc
    return res[P]

print(divide(10, 10))
# [6, 0, 1, 0, 1, 0, 1, 0, 1, 0]