6
$\begingroup$

While raiding a tropical island, 6 pirates have an incredibly unlucky day.

While they scoured the island in search of treasure, one of them was infected with the Fanatic Fever, a disease which hits the pirate right in his greatest strength. (As everybody knows, a pirates greatest strength is his perfect rationality.)

A healthy pirate will always act in a certain way, following lower number rules first then higher numbered rules:

  1. They will always choose action a over action b if action a means they have a higher chance of survival.

  2. They will always choose action a over action b if action a and b have equal chances of survival, and action a leads to higher expected gold. Note: expected gold is defined as such: an x percent chance of getting y gold is x*y expected gold.

  3. All else equal they prefer to see other pirates die. (They are ambivalent about whether more pirates die after they are dead.)

  4. They randomly choose between actions they are ambivalent about in an entirely unpredictable fashion. In general, if there are n actions, all of which are equally preferable, they will choose each with 1/n probability.

However, a pirate infected with the fanatic fever is different. He will always, and only, vote for plans that involve the oldest pirate getting the most gold. If they are the oldest pirate, they can and will only propose such plans.

As you may know, pirates have a particular method of distributing the gold pieces they get from piracy. The oldest pirate proposes a plan which says exactly how many gold pieces each pirate will receive. Gold pieces cannot be cut, so each pirate must receive a whole number of gold pieces in any given plan.

Next, starting with the oldest pirate, and in order such that no younger pirate votes before an older pirate, each pirate publicly votes yes or no to the plan. Every pirates vote counts once except the oldest pirate's vote which counts one and a half times. The votes are tallied up. If there are more yesses, the gold is distributed as proposed. Otherwise, the oldest pirate is executed and they restart. No two pirates are exactly the same age.

Although all pirates know that exactly one of them is infected with fanatic fever, and all other pirates are healthy, no healthy pirate initially knows who is infected (although each pirate does know if they in particular are infected). Every healthy pirate initially believes that every other pirate has an equal chance of being infected.

Now, these pirates are actually so unlucky, that in addition to one of them being infected, they only found a single gold piece.

Question: When it comes time to distribute the gold pieces, what should the oldest pirate propose assuming he is healthy, and how likely is he to survive assuming each other pirate has an equal chance of being infected? For completeness, give every possible scenario with its probability. Remember that none of the other pirates other than the infected one know that the oldest pirate is not infected.

Challenge: Generalize for N pirates.

Extra hard challenge: Generalize for N pirates and X gold.

Impossible (Literally?) challenge: Generalize for N pirated, X gold, and Z of the pirates are infected with fanatic fever.

$\endgroup$
  • $\begingroup$ Answer to the impossible challenge 1 probability unit defines as equal to the odds of survivng in the N pirated, X gold, and Z of the pirates are infected with fanatic fever, case. $\endgroup$ – Going hamateur Aug 14 '15 at 16:11
  • $\begingroup$ Clarifier- at first you indicate that the oldest pirate can be infected, but later you state that they are not. Which is the case? $\endgroup$ – Patrick N Aug 14 '15 at 16:39
  • 1
    $\begingroup$ @Patrick You as the puzzle solver know that the oldest pirate is not infected. The oldest pirate, as a healthy pirate, also knows this. However, he COULD have been infected, and none of the other healthy pirates initially knows that he wasn't. Essentially, he is healthy, but this is not common knowledge. $\endgroup$ – Ethan Fine Aug 14 '15 at 16:42
  • $\begingroup$ Does every pirate who is not infected believe that every other pirate is equally likely to be infected? $\endgroup$ – f'' Aug 14 '15 at 17:01
  • 1
    $\begingroup$ @Tyler Correct. Otherwise I wouldn't have specified that they start voting with the oldest and move toward the youngest. I'll clarify. $\endgroup$ – Ethan Fine Aug 15 '15 at 4:03
1
$\begingroup$

I have thougth about the N pirates challenge a little bit, but probably I made a mistake somewhere in my reasoning... but here we go. It's a little long and confusing, and english is not my main language, but anyway I'll do my best. Feel free to correct me or ask for clarifications.

Summary:

For n any positive integer and N number of pirates, and Z the position of the infected (1 the youngest, N the oldest):

  • If N = 2^n or N = 2^(n-1)+4, all pirates are saved, the oldest has the coin
  • If 2^(n-1) + 4 < N < 2^n and Z between 2^(n-2)+2 and 2^(n-1)+4, all die until pirate 2^(n-1) + 4, the oldest has the coin.
  • If 2^(n-1) + 4 < N < 2^n and Z < 2^(n-2)+2, all die until pirate 2^(n-1) + 2, the oldest has the coin.
  • If 2^(n-1) + 4 < N < 2^n and Z > 2^(n-1)+2, all die until pirate 2^(n-1) + 2, one of the pirates < 2^(n-2)+2 gets the coin.
  • Every other case, all pirates die until pirate 2^(n-2)+2, one of the pirates < 2^(n-3)+2 gets the coin.

First of all, we define a "safe" pirate if he will survive, no matter where the infected is. And we define a "desperate" pirate (or "despirate") if there is a chance of death, even the littlest.

We will also call the pirates from 1 to N, 1 the youngest, N the oldest.

If there where no infected pirate, we can see that a safe pirate has always his vote, the votes of the despirates in his turn and one bribed pirate of his choice.

We can also see that any pirate with number less than a safe pirate becomes a safe pirate, because it will never be his turn. So, a pirate behind a safe pirate will always vote death, unless it is his closest (and greater than him) safe pirate's turn, or if he's bribed. That lets us with safe pirates at N = 2^n + 2.

But now, with one infected pirate, we can`t know if he is one of the desperate or the safe pirates. If he is one of the desperate, then if we bribe one pirate, we lose the infected vote. If we don't bribe anyone, then we lose the bribed pirate's vote, so in any case we have one vote less than the no infected case. It's analogous with the case of the infected being one of the safe pirates, either we lose the bribed pirate's vote, or the infected, leaving us in the same state as with no infected.

That said, our first pirate will decide to keep the coin. Now it's time to decide when a pirate is safe and when is not. Our first pirate will always think he is in the worst case scenario, that is, the infected is one of the desperate pirates. This is the same as to think that there is not an infected pirate and he can't bribe anyone.

Then, a safe pirate is one pirate that has half of the pirates being desperate (counting him). So if the previous safe pirate is n, the next safe pirate will be 2n. All pirates between n and 2n are despirates, because if the infected happens to be among them, they will die if his turn comes, so all of them must vote for 2n to be 100% sure of surviving.

In Tyler Seacrest answer and comment we can see that pirates 5, 6 and 7 are despirates (they can die if the infected is one of them), so pirate 8 is safe, he has the votes of 5, 6, 7 and 8 at least (one more if the infected is not amongst them). The next safe pirate will be 16, then 32, 64... all powers of 2. Even 2 and 4 are safe pirates, so we can say that:

If N = 2^n, with n natural number, all of them will survive, with the oldest pirate keeping the coin.

Now, if N is not 2^n we can say wolog that 2^(n-1) < N < 2^n for some n. Let's say that N = 2^n - 1. If the infected pirate is among the despirates, the he will die. If the infected is among the safe ones and all the desperate pirates vote for him, he would survive. But as the number of pirates at this point is odd, he have one more vote than needed, meaning that under the same circunstances, pirate N-1 would survive too. So pirate N-1 will vote to kill him, as the chances of survival are the same (pirate N-2 can't do that to pirate N-1 because he won't get enough votes to survive). Also, every other pirate should vote to kill him, because if they can save him, they can also save the next pirate, so is best to kill him and save the next.

Note that in this case, every pirate votes to kill but the oldest and the infected, giving us the information about who the infected is, changing the safe-desperate pattern. Now they know exactly how many votes they will get for sure.

At this moment, pirate 2^(n-1) + 2 (let's call him M) is safe if the infected is between 1 and 2^(n-2)+2 (both included) or greater than 2^(n-1) + 2. If the infected is not in that interval, the greatest safe pirate will be 2^(n-1) + 4. In both cases the pirate M and all pirates < M will survive, so they vote to kill N and get the information. The next pirates are killed until pirate 2^(n-1) + 4 (let's call him L). If L is the first pirate to vote (meaning that the total number of pirates is L, so no one has any information), all pirates from him to 2^(n-2)+2 will vote to save him, in fear of the infected being amongst them. If he's not the first but the infected happens to be amongst them, they will also save him. But if he is not the first and the infected is not amongst them, he and the next one will be killed, and M will be saved. For 2^(n-1) + 3 there are not enough pirates in fear to stop the killing, so he will die, and pirate M depends on where the infected shows to know if he survives or not. For 2^(n-1) + 2 the same as above, he is killed because not enough pirates are afraid if he is unlucky (and the slaughter will continue until pirate 2^(n-2) + 2, who emerges victorious but poor). For 2^(n-1) + 1 he will be killed either way, and again 2^(n-2) + 2 wins using the coin to bribe someone.

I think that's all, sorry for the long answer.

$\endgroup$
  • $\begingroup$ Great answer. I didn't expect any more answers to this one, but I think you got it. Also "despirate" is awesome. $\endgroup$ – Ethan Fine Nov 18 '15 at 17:18
  • $\begingroup$ Thanks! I'll try the other challenges soon. If I get a solution I will post it :) $\endgroup$ – BianB BB Nov 19 '15 at 8:37
  • 1
    $\begingroup$ You've made a mistake here: "Note that in this case, every pirate votes to kill but the oldest and the infected, giving us the information about who the infected is". If a pirate is rational and sees that X people want the plan to pass, and Y>>X people want the plan to fail, he knows the plan will fail no matter what, so his vote does not affect the outcome, so he is ambivalent and chooses how to vote at random. This means that you can't always identify the infected by round 2. $\endgroup$ – Ninety-Three Dec 3 '15 at 15:36
  • $\begingroup$ You are right, if I have time I'll edit it $\endgroup$ – BianB BB Dec 7 '15 at 11:01
2
$\begingroup$

For the easiest case (Oldest to Youngest is A - F)

Pirate A will propose giving herself the gold, which will succeed with probability 4/5 from pirate A's perspective.

An important point, which we will establish later, is that C is certain to survive or fevered. If C is fevered, it might be possible in some hypothetical situation that C dies, but in that case it will be certain that D-F survive. So C-F all feel safe and are just after the most gold and most blood, or are fevered.

Pirate A can only appease one of C-F with gold, but if she picks the fevered pirate, she can't generate the 3.5 required votes, and thus only succeeds with probability at most 4/5 and no gold. So Pirate A proposes "Give the gold to me", gets pirate B's vote, and hopes to get the fevered pirate amoung C-F (probability 4/5).

Pirate B votes for A's proposal since he is pretty much shark bait otherwise. If B voted against A's proposal, then by how the vote turned out we'd know who the fevered pirate was. If B proposes "Give the gold to me", since C-F all feel safe, at least three votes will be for B's blood, and this is a sure loss. Similarly, B can only appease one pirate with gold, and that is not enough to swing the votes.

Pirate C is safe if not fevered, because at that point she knows who the fevered pirate is / was. If one of D-F is fevered, Pirate C can succeed with "Give the gold to me". Otherwise, C can offer D or E a gold and at least survive. At that point, D or E will take the gold, since D's best plan would be to offer the gold to F. If C is fevered, then she'll walk the plank but D will survive with the offer of a gold to F.

$\endgroup$
  • $\begingroup$ Correct. In a few days I'll give you the check mark if nobody solves the more complicated cases. $\endgroup$ – Ethan Fine Aug 15 '15 at 22:25
  • $\begingroup$ @EthanFine: Leave it open as long as you like; I'd like to see solutions for more pirates. For $N = 7$, you get very interesting behavior. Suppose Z is the additional (oldest) pirate. Then if Z proposes to give the gold to himself, it becomes complicated. At first I thought A would vote for Z's plan, since A can't guarantee her own survival if Z's plan fails. But Z's plan fails, even with A's vote, exactly if B is fevered, which is exactly when A doesn't survive. Since voting yes doesn't help A's survival, she votes no and dooms Z's plan. $\endgroup$ – Tyler Seacrest Aug 16 '15 at 3:21

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.