31
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I believe there is no good strategy for N between 800 and 1200; all leaders will be eaten. In the bottom 800 there are 3 factions: at most 200 satisfied (with gold), at least 400 dissatisfied (with chance for gold but no gold), and 200 flip-flops (top of the 800, with chances for the sharks if the plan isn't eventually accepted.). The flipflops will keep feeding sharks for fun, as long as they can join ranks with the satisfied and get the split accepted. When the risk for dissatisfied reaching majority appears (and culling all flipflops for fun) flipflops will stop the carnage. $\endgroup$ – SF. May 15 '14 at 19:45
  • $\begingroup$ @SF.: The interesting things start to happen at 400. There is a good strategy for some N between 800 and 1200. $\endgroup$ – Ross Millikan May 15 '14 at 20:16
  • $\begingroup$ How do you placate the 600 bloodthirsty jerks with nothing to lose then? $\endgroup$ – SF. May 15 '14 at 20:51
  • $\begingroup$ @SF.: I believe we only have to get one proposal through. People are then stuck with what they got from that proposal. Priority 1 is powerful and can buy votes without using gold. $\endgroup$ – Ross Millikan May 15 '14 at 20:53
  • $\begingroup$ Yes, but it can only buy 200 votes in an 800+ population. Most of the remainder has nothing to lose by voting against, and then point 3 takes precedence. 200 for, 600 against, and the remainder - about to die (obviously for, but outvoted). Also, let's move to chatroom. $\endgroup$ – SF. May 15 '14 at 20:56
32
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ This is the expected solution. Good work. $\endgroup$ – Ross Millikan Jun 5 '14 at 3:02
10
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Hmm. I'll have to take a closer look at N > 200 later then. $\endgroup$ – Kevin May 15 '14 at 18:29
  • $\begingroup$ Sorry, I had a typo (200 instead of 100 coins) That means your 400's are correct and the interesting case is >400 $\endgroup$ – Ross Millikan May 15 '14 at 20:15
  • $\begingroup$ It's probably easier to graphically represent it if you start from meekest with your numbering to keep it consistent since that is actually what matters in the problem. Each meek pirate has to be offered more than they could get in any further iteration, which may actually make 1 gold insufficient at > 400 as well potentially. $\endgroup$ – AJ Henderson May 15 '14 at 20:34
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ As I saw the problem, once the gold is divided we are done. We don't have to satisfy a recurring division. I think success comes up to 400 and at $400+2^n$, starting at $n=0$ $\endgroup$ – Ross Millikan May 15 '14 at 20:37
  • $\begingroup$ Yes, we don't have to. It was just to illustrate the events of population one-shorter than threshold. $\endgroup$ – SF. May 15 '14 at 20:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.