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:
They will always choose action a over action b if action a means they have a higher chance of survival.
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.
All else equal they prefer to see other pirates die. (They are ambivalent about whether more pirates die after they are dead.)
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.
Answer
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.
No comments:
Post a Comment