A group of N pirates has come by a chest containing 200 gold coins. Their rules require that the coins be distributed by the following approach. The pirates are ranked from fiercest to meekest and all pirates know the ranking. The fiercest must propose a division, which is put to majority vote with the fiercest voting and winning ties. If the proposal wins, it is implemented. If not, the fiercest is fed to the sharks and the responsibility falls to the (newly promoted) fiercest. The pirates are selfish and quite rational, with the following priorities:
- Stay alive
- Get as much gold as possible, as long as 1 is satisfied
- If 1 is satisfied and two options are equivalent in terms of gold, feed somebody to the sharks by preference.
Depending on N, what happens? To be complete, your answer should deal with large values of N. Source: I first saw it in a Martin Gardner column.
Answer
Let's put the number of coins at $c$ and see what happens if we increase $n$. We'll number the pirates from meekest ($1$) to fiercest ($n$).
$\begin{array}{rrrll} \begin{array}{c}\text{Nr. of pirates}\end{array} & \begin{array}{c}\text{Pirate} \\ \text{meekest to fiercest}\end{array} & \begin{array}{c}\text{Nr. of coins}\end{array} & \begin{array}{c}\text{Vote}\end{array} & \\ \hline 1 & 1 & c & \text{yes} \\ \\ 2 & 1 & 0 & \text{no} \\ & 2 & c & \text{yes} & \text{breaks tie} \\ \\ 3 & 1 & 1 & \text{yes} \\ & 2 & 0 & \text{no} \\ & 3 & c-1 & \text{yes} \\ \\ 4 & 1 & 0 & \text{no} \\ & 2 & 1 & \text{yes} \\ & 3 & 0 & \text{no} \\ & 4 & c-1 & \text{yes} & \text{breaks tie} \\ \\ 5 & 1 & 1 & \text{yes} \\ & 2 & 0 & \text{no} \\ & 3 & 1 & \text{yes} \\ & 4 & 0 & \text{no} \\ & 5 & c-2 & \text{yes} \\ \\ \text{...} \\ \\ 2c & 1 & 0 & \text{no} \\ & 2 & 1 & \text{yes} \\ & 3 & 0 & \text{no} \\ & \text{...} \\ & n & 1 & \text{yes} & \text{breaks tie} \\ \end{array}$
If we define a solution as stable if nobody gets fed to the sharks, we can say that all solutions so far have been stable. This is because for each $n$, there are more or at least as much (in which case the tie is broken) pirates who would be worse off in the solution for $n-1$.
But now, we're at $n = 2c + 1$. Are we getting ready for carnage? Not quite:
$\begin{array}{rrrll} \begin{array}{c}\text{Nr. of pirates}\end{array} & \begin{array}{c}\text{Pirate} \\ \text{meekest to fiercest}\end{array} & \begin{array}{c}\text{Nr. of coins}\end{array} & \begin{array}{c}\text{Vote}\end{array} & \\ \hline 2c+1 & 1 & 1 & \text{yes} \\ & 2 & 0 & \text{no} \\ & 3 & 1 & \text{yes} \\ & \text{...} \\ & n-1 & 0 & \text{no} \\ & n & 0 & \text{yes} \\ \end{array}$
Here, the fiercest pirate can escape alive, but without gold.
Okay, but now surely the sharks are getting fed? Let's see.
$\begin{array}{rrrll} \begin{array}{c}\text{Nr. of pirates}\end{array} & \begin{array}{c}\text{Pirate} \\ \text{meekest to fiercest}\end{array} & \begin{array}{c}\text{Nr. of coins}\end{array} & \begin{array}{c}\text{Vote}\end{array} & \\ \hline 2c+2 & 1 & 0 & \text{no} \\ & 2 & 1 & \text{yes} \\ & 3 & 0 & \text{no} \\ & \text{...} \\ & n-2 & 1 & \text{yes} \\ & n-1 & 0 & \text{no} \\ & n & 0 & \text{yes} & \text{breaks tie} \\ \end{array}$
The fiercest pirate now broke the tie to stay alive.
How about $n = 2c + 3$ then?
$\begin{array}{rrrll} \begin{array}{c}\text{Nr. of pirates}\end{array} & \begin{array}{c}\text{Pirate} \\ \text{meekest to fiercest}\end{array} & \begin{array}{c}\text{Nr. of coins}\end{array} & \begin{array}{c}\text{Vote}\end{array} & \\ \hline 2c+3 & 1 & 1 & \text{yes} \\ & 2 & 0 & \text{no} \\ & 3 & 1 & \text{yes} \\ & \text{...} \\ & n-3 & 0 & \text{no} \\ & n-2 & 0 & \text{no} \\ & n-1 & 0 & \text{no} \\ & n & 0 & \text{yes} & \text{shark bait} \\ \end{array}$
Here, finally, at $n = 2c + 3$, we reach our first unstable solution. The fiercest pirate can buy $c$ votes, adds his own vote for a total of $c+1$, but the opposition has $c + 2$ votes.
Note that here, pirate $n-3$ is pirate $n-2$ from the solution before it. Voting $\text{no}$ yields a coin. Pirates $n-2$ and $n-1$ get no gold by voting against this proposal, but as per the third rule, vote to feed the sharks.‡
But does that mean that from now on, all pirates get their feet wet? Not at all.
$\begin{array}{rrrll} \begin{array}{c}\text{Nr. of pirates}\end{array} & \begin{array}{c}\text{Pirate} \\ \text{meekest to fiercest}\end{array} & \begin{array}{c}\text{Nr. of coins}\end{array} & \begin{array}{c}\text{Vote}\end{array} & \\ \hline 2c+4 & 1 & 1 & \text{yes} \\ & 2 & 0 & \text{no} \\ & 3 & 1 & \text{yes} \\ & \text{...} \\ & n-4 & 0 & \text{no} \\ & n-3 & 0 & \text{no} \\ & n-2 & 0 & \text{no} \\ & n-1 & 0 & \text{yes} & \text{potential shark bait} \\ & n & 0 & \text{yes} & \text{breaks tie} \\ \end{array}$
Now both the fiercest pirate and the almost-as-fierce pirate are voting for their lives, since the solution with one pirate less is unstable and will see the almost-as-fierce pirate being fed to the sharks. The fiercest pirate breaks the tie and this solution is stable.
$\begin{array}{rrrll} \begin{array}{c}\text{Nr. of pirates}\end{array} & \begin{array}{c}\text{Pirate} \\ \text{meekest to fiercest}\end{array} & \begin{array}{c}\text{Nr. of coins}\end{array} & \begin{array}{c}\text{Vote}\end{array} & \\ \hline 2c+5 & 1 & 0 & \text{no} \\ & 2 & 1 & \text{yes} \\ & 3 & 0 & \text{no} \\ & \text{...} \\ & n-5 & 1 & \text{yes} \\ & n-4 & 0 & \text{no} \\ & n-3 & 0 & \text{no} \\ & n-2 & 0 & \text{no} \\ & n-1 & 0 & \text{no} \\ & n & 0 & \text{yes} & \text{shark bait} \\ \\ 2c+6 & 1 & 0 & \text{no} \\ & 2 & 1 & \text{yes} \\ & 3 & 0 & \text{no} \\ & \text{...} \\ & n-6 & 1 & \text{yes} \\ & n-5 & 0 & \text{no} \\ & n-4 & 0 & \text{no} \\ & n-3 & 0 & \text{no} \\ & n-2 & 0 & \text{no} \\ & n-1 & 0 & \text{yes} \\ & n & 0 & \text{yes} & \text{shark bait} \\ \\ 2c+7 & 1 & 0 & \text{no} \\ & 2 & 1 & \text{yes} \\ & 3 & 0 & \text{no} \\ & \text{...} \\ & n-7 & 1 & \text{yes} \\ & n-6 & 0 & \text{no} \\ & n-5 & 0 & \text{no} \\ & n-4 & 0 & \text{no} \\ & n-3 & 0 & \text{no} \\ & n-2 & 0 & \text{yes} \\ & n-1 & 0 & \text{yes} \\ & n & 0 & \text{yes} & \text{shark bait} \\ \\ 2c+8 & 1 & 0 & \text{no} \\ & 2 & 1 & \text{yes} \\ & 3 & 0 & \text{no} \\ & \text{...} \\ & n-8 & 1 & \text{yes} \\ & n-7 & 0 & \text{no} \\ & n-6 & 0 & \text{no} \\ & n-5 & 0 & \text{no} \\ & n-4 & 0 & \text{no} \\ & n-3 & 0 & \text{yes} & \text{potential shark bait} \\ & n-2 & 0 & \text{yes} & \text{potential shark bait} \\ & n-1 & 0 & \text{yes} & \text{potential shark bait} \\ & n & 0 & \text{yes} & \text{breaks tie} \\ \end{array}$
And we've found a stable one again.
$\begin{array}{rrrll} \begin{array}{c}\text{Nr. of pirates}\end{array} & \begin{array}{c}\text{Pirate} \\ \text{meekest to fiercest}\end{array} & \begin{array}{c}\text{Nr. of coins}\end{array} & \begin{array}{c}\text{Vote}\end{array} & \\ \hline 2c+9 & 1 & 1 & \text{yes} \\ & 2 & 0 & \text{no} \\ & 3 & 1 & \text{yes} \\ & \text{...} \\ & n-9 & 0 & \text{no} \\ & n-8 & 0 & \text{no} \\ & n-7 & 0 & \text{no} \\ & n-6 & 0 & \text{no} \\ & n-5 & 0 & \text{no} \\ & n-4 & 0 & \text{no} \\ & n-3 & 0 & \text{no} \\ & n-2 & 0 & \text{no} \\ & n-1 & 0 & \text{no} \\ & n & 0 & \text{yes} & \text{shark bait} \\ \end{array}$
And so on.
When $n > 2c$, we'll see more and more large runs of downvoting pirates, until the number of pirates upvoting to save their lives becomes equal to the number of downvoters and we find a stable solution again.
This yields the following formula for stable solutions: $$ n \leq 2c \lor n = 2c + 2^z\,|\,z \in \mathbb Z_{\ge 0}$$
The procedure by which to distribute the coins is based on the fact that a pirate can only buy votes if coins are given to the opposite pirates from the next stable solution.
It is as follows:
- For $n \leq 2c$ give a coin to every pirate with the same parity as $n$, with any left over coins going to the fiercest pirate.
- For $2c + 2^{z-1} < n \leq 2c + 2^z\,|\,z \in \mathbb Z_{\ge 0}$ start with the meekest pirate with the opposite parity of $z$ and move up in ferocity.†
‡: I prefer to think of the pirates as kind hearted people who care for the sharks and don't want them to go hungry.
†: It can be argued that if a solution is known to be unstable, all other pirates will vote no, since it doesn't matter who gets the coins — they won't get to keep them. But for the stable solution, it is necessary to distribute the coins like this.
No comments:
Post a Comment