Puzzle of the Pirate Booty
This was originally posted as a PDF, but I converted it into a blog post here. The PDF is still available here.
If there are $P$ Perfectly Rational Pirate Logicians (PPRLs) and $G$ indivisible gold coins, how will they divide the coins (following the rules outlined in this Riddler post)?
Let $\{p_1, p_2, \ldots, p_P\}$ be the set of pirates, where $p_1$ is the highest ranked pirate, and let their shares of the gold be $\{g_1 , g_2, \ldots, g_P\}$, with $\sum g_i = G$. First, examine the base cases. If $P = 1$, then $g_1 = G$. Next, if $P = 2$, then $g_1 = G$, and $g_2 = 0$.
Now, let's assume that $G\ge \text{ceil}{(P-1)/2}$. If $P=3$, $g_1=G-1$ and $g_3=1$. This is because $p_3$ knows that if he votes against $p_1$, then $p_1$ would be killed, and the $P=2$ scenario would play out, with $p_3$ getting nothing. Therefore $p_3$ votes with $p_1$. If $P=4$, then $p_1$ will bribe the loser of the $P=3$ scenario, $p_{P-1}=p_3$, so $g_1=G-1$, and $g_2=1$. Then, for $P>4$, we have
\begin{align}
g_1 &= G - \text{ceil}{(P-1)/2} \\
g_{2k+1} &= 1 \\
g_{2k} &= 0
\end{align}
for every integer $k>0$ with $2k+1\le P$. This is also presented in the table:
$P$ | $g_1$ | $g_2$ | $g_3$ | $g_4$ | $g_5$ | $g_6$ | $\dots$ |
---|---|---|---|---|---|---|---|
$6$ | $G-2$ | $0$ | $1$ | $0$ | $1$ | $0$ | |
$5$ | $G-2$ | $0$ | $1$ | $0$ | $1$ | ||
$4$ | $G-1$ | $0$ | $1$ | $0$ | |||
$3$ | $G-1$ | $0$ | $1$ | ||||
$2$ | $G$ | 0 | |||||
$1$ | $G$ |
Note that in the case that $G=\text{ceil}{(P-1)/2}$, e.g. $P=3$ and $G=1$, $g_1=0$ and $g_3=1$. This is an interesting case because it's informed by the bloodthirsty rule. If the captain suggests that he gets the only gold coin, then obviously the 2nd-in-command will vote against it. But the third-in-command will vote it against it too, even though he knows that then the 2nd-in-command gets the gold piece. This is because if he doesn't get any gold, he can at least see some killing. Thus, the captain has to give up his gold piece in favor of staying alive.
Finally, let's look at the case where $0<G<\text{ceil}{(P-1)/2}$. E.g., $G=1$ and $P=5$. In this case, the captain must die. Since three votes are needed for any proposal, and the captain votes for his self-preservation and any other pirate will vote for greed, he can only get two votes total. Thus, the first $\text{ceil}{(P-1)/2}-G$ pirates will be killed this way, and then the distribution above will kick in.