Pirates and gold coins

Question

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:

1. Stay alive
2. Get as much gold as possible, as long as 1 is satisfied
3. 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 1

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$).

Nr. of pirates	Pirate meekest to fiercest	Nr. of coins	Vote
1	1	c	yes
2	1 2	0 c	no yes breaks tie
3	1 2 3	1 0 c-1	yes no yes
4	1 2 3 4	0 1 0 c-1	no yes no yes breaks tie
5	1 2 3 4 5	1 0 1 0 c-2	yes no yes no yes
...
2c	1 2 3 ... n	0 1 0 1	no yes no yes breaks tie

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:

Nr. of pirates	Pirate meekest to fiercest	Nr. of coins	Vote
2c+1	1 2 3 ... n-1 n	1 0 1 0 0	yes no yes no yes

Here, the fiercest pirate can escape alive, but without gold.

Okay, but now surely the sharks are getting fed? Let's see.

Nr. of pirates	Pirate meekest to fiercest	Nr. of coins	Vote
2c+2	1 2 3 ... n-2 n-1 n	0 1 0 1 0 0	no yes no yes no yes breaks tie

The fiercest pirate now broke the tie to stay alive.

How about $n = 2c + 3$ then?

Nr. of pirates	Pirate meekest to fiercest	Nr. of coins	Vote
2c+3	1 2 3 ... n-3 n-2 n-1 n	1 0 1 0 0 0 0	yes no yes no no no yes shark bait

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.

Nr. of pirates	Pirate meekest to fiercest	Nr. of coins	Vote
2c+4	1 2 3 ... n-4 n-3 n-2 n-1 n	1 0 1 0 0 0 0 0	yes no yes no no no yes potential shark bait yes breaks tie

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.

Nr. of pirates	Pirate meekest to fiercest	Nr. of coins	Vote
2c+5	1 2 3 ... n-5 n-4 n-3 n-2 n-1 n	0 1 0 1 0 0 0 0 0	no yes no yes no no no no yes shark bait
2c+6	1 2 3 ... n-6 n-5 n-4 n-3 n-2 n-1 n	0 1 0 1 0 0 0 0 0 0	no yes no yes no no no no yes yes shark bait
2c+7	1 2 3 ... n-7 n-6 n-5 n-4 n-3 n-2 n-1 n	0 1 0 1 0 0 0 0 0 0 0	no yes no yes no no no no yes yes yes shark bait
2c+8	1 2 3 ... n-8 n-7 n-6 n-5 n-4 n-3 n-2 n-1 n	0 1 0 1 0 0 0 0 0 0 0 0	no yes no yes no no no no yes potential shark bait yes potential shark bait yes potential shark bait yes breaks tie

And we've found a stable one again.

Nr. of pirates	Pirate meekest to fiercest	Nr. of coins	Vote
2c+9	1 2 3 ... n-9 n-8 n-7 n-6 n-5 n-4 n-3 n-2 n-1 n	1 0 1 0 0 0 0 0 0 0 0 0 0	yes no yes no no no no no no no no no yes shark bait

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 kindhearted 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.}

Answer 2

I believe pirate 1 (fiercest) should give every odd-numbered pirate (3rd fiercest, 5th, etc.) 1 gold, starting from the least-fierce end, and take the remainder (if any) for himself. This has the unintuitive effect that if there are more than 400 pirates, the only way for the fiercest to survive is to take none for himself.

Let's start with small N and use inference:

N = 2: 1 takes all gold (200) for himself. He votes yes, 2 votes no, 1, being fiercest, breaks tie and takes all the gold

N = 3: 1 needs one vote for him. If he is killed, 3 gets nothing, so if he gives 3 1 piece, 3 votes for him, he wins 2-1.

N = 4: 1 just needs one other vote (and he breaks the tie by being fiercest). If he is killed, 3 gets nothing (as he becomes 2 in the previous case)

N = 5: 1 needs two votes, so he gives 1g to the two who would get nothing if he were killed, the current 3 and 5.

(somewhat) graphically:

N = 2:
        1 = 200
        2 = 0
N = 3:
        1 = 199
        2 = 0
        3 = 1
N = 4:
        1 = 199
        2 = 0
        3 = 1
        4 = 0
N = 5:
        1 = 198
        2 = 0
        3 = 1
        4 = 0
        5 = 1

So we see that the fiercest pirate gives 1 gold to those who would get nothing for N-1. These happen to always be the odd-numbered pirates. Once the money runs out (N > 400), only the (odd) least fierce pirates get paid, since if they did not, enough would object to kill the

Answer 3

Oh my. For large N ( > 400) this gets an exponential structure of strings of carnage that can be stopped at certain points: a simple strategy exists for each pirate of fierceness 400+100*2^n (negative n allowed until we start getting fractional pirates). No optimal strategy exists for the remaining leaders; they die.

Let's start with the first carnage at N>800.

There's at most 200 pirates who got any gold, and would prefer to keep it, but they have no say in it, for there's another 600 blood-thirsty jerks who believe they can murder the fiercest with full impunity and have nothing to lose (and either gain a chance for gold, or not gain anything).

The leaders are slaughtered until the total number drops to 800. Then the leader distributes gold to the bottom 600 at random (1 piece per pirate though). Each of those on the bottom, who got a gold coin will vote to keep it, because they won't earn more anyway, and have a chance to lose it. Then the top 200 including the tie-breaking boss joins with approval and with 400+tie votes they outvote these out of bottom 600 who didn't get any gold.

Now, assume one of the top 200 is an idiot and votes for sharks at the critical point. 200 satisfied with their coins and 199 currently-victims won't outvote the 400 who want blood (and money). The 400 keep killing until there's only 600 pirates left: 300 without gold, 200 with gold, and 100 potential victims if they don't come to agreement right now: gold distributed at random to 200 out of the bottom 500, the 100 come out alive, 300:300.

Again, assume an idiot botches the voting. 250 blood-thirsty pirates slaughter 50 leaders, then best 50 of them join the 200 satisfied to vote own survival.

You see the pattern?

Let's try upwards. In our 800-pirate population we have 600 blood-thirsty jerks, who need to be outvoted by 200 with gold and a certain number who just wants to live. Well, that number appears to be 400, bringing the total number to 1200. But if the population is bigger, these 400 know they can kill with impunity (and won't get any gold anyway) so 1200 is the next population threshold.

So, 25, 50, 100, 200, 400...

500 = 400+100, 600=400+200, 800=400+400, 1200=400+800

Each pirate of fierceness 400+100*2^n has the opportunity to come out of this penniless, alive, and stop the slaughter, in exchange for distributing all gold to the bottom 3/4 of the band, randomly.

Each other pirate above these specific ones, I think 400, correct me if I'm wrong, gets fed to the shark no matter what they offer.