xxviii. Pirates and Gold

Problem. $n$ ranked pirates split $G$ coins. The most senior proposes a split; everyone votes; it passes with at least half the votes (the proposer votes too), otherwise the proposer is thrown overboard and the next one proposes. Pirates want to survive, then maximize coins, then see others thrown overboard (so they vote yes only for a strict improvement).

Answer (backward induction): the proposer buys the $\lceil n/2\rceil -1$ cheapest votes, paying each such pirate one coin more than they would get in the $(n-1)$-pirate solution. For 5 pirates and 100 coins: $98,0,1,0,1$.

vector<long long> piratesSplit(int n, long long G) {   // pirate 0 proposes; passes with >= half the votes; returns coins per pirate (needs G large enough)
    vector<long long> cur{G};                           // solution with 1 pirate
    for (int k = 2; k <= n; k++) {
        // cur = split among the k - 1 junior pirates if the proposer dies; buy the cheapest votes
        int need = (k + 1) / 2 - 1;                     // yes votes needed besides the proposer
        vector<int> idx(k - 1); iota(all(idx), 0);
        stable_sort(all(idx), [&](int a, int b) { return cur[a] < cur[b]; });
        vector<long long> nxt(k, 0); long long spent = 0;
        for (int t = 0; t < need; t++) { nxt[idx[t] + 1] = cur[idx[t]] + 1; spent += cur[idx[t]] + 1; }
        nxt[0] = G - spent; cur = nxt;
    }
    return cur;
}

Proof: buying the cheapest votes is optimal

If the proposal fails, pirates $\mathrm{2..}n$ play the $(n-1)$-pirate game, whose outcome gives pirate $j$ some $c_j$ coins (induction). A pirate votes yes iff offered more than $c_j$, so a yes vote costs at least $c_j+1$, and offering exactly that buys it. The proposer needs $\lceil n/2\rceil$ votes including their own, so they pay for the $\lceil n/2\rceil -1$ smallest values of $c_j+1$ and keep the rest; any other choice pays at least as much. Valid while $G$ covers the bribes (for $n>2G+2$ the pattern changes and some proposers die). Checked against exhaustive search over all allocations for $n\le 5$, $G\le 6$, and the classic $98,0,1,0,1$.