A prison contains N prisoners who are all scheduled to be executed. The warden offers them a small glimmer of hope for one to survive. He has a box containing N gold coins and 1 red coin. One by one the prisoners will take turns randomly selecting a number of coins from the box (without replacement) until the box is empty. The prisoner who ends up with the red coin will die. Of the remaining prisoners, if a single one has the most gold coins he will be set free and the rest of the prisoners will die. If there is a tie for the most gold coins, all the prisoners die.
Additional notes:
- On their turn each prisoner declares how many coins they want and receive them all at once.
- All prisoners see the results of the prior prisoners’ selections.
- Each prisoner will act in his own self-interest, trying to save himself.
- The prisoners are jerks, so if one knows he is definitely going to die he will try to ensure everyone dies.
You are the first prisoner to go. How many coins should you pull from the box, and what are your chances of survival?
(In reply to
re(2): solution - Follow up by tomarken)
Funny you should ask. I was playing with this, and I was going to post that there are other ways to have the same chance of surviving as Dej Mar's solution, and they are a little more suspenseful. Further, there is an argument that Dej Mar's solution is not the one that Prisoner 1 will take.
With 10 prisoners, Dej Mar would have the first prisoner pull 6 coins, and survive with probability 5/11. If he pulls the red coin, then prisoner 2 survives.
But you could also pull 5 coins with the same probability of survival. If you do not pull a red coin (with probability 6/11), then the second prisoner knows that he has no chance of surviving. Since he is a jerk, he pulls 1 coin or 5 coins. If his single pull is red (with probability 1/6) or if all 5 coins he pulls are gold (with probability 1/6), then everybody dies. Otherwise, first prisoner's chance of survival is (6/11)*(5/6) = 5/11.
And Prisoner 1 could also pull 4 coins with the same probability of survival. If he does not pull a red coin (with probability 7/11), then the second prisoner's best chance to survive is to pull 5 coins. If prisoner 2 does not pull a red coin (with probability 2/7), then prisoner 2 survives. Otherwise, prisoner 1 survives, and his overall probability of survival is (7/11)*(5/7) = 5/11.
Pulling 3 coins does not work. Either prisoner 2 or prisoner 3 will be the survivor.
So, there are three different ways that Prisoner 1 can have a 5/11 probability of survival. Does he prefer one way over the other? The answer is YES! PRISONER 1 PREFERS TO PULL 5 COINS INITIALLY, NOT 6 or 4. THIS IS THE ONLY WAY THAT THERE IS A POSSIBILITY THAT IF HE DOES NOT SURVIVE, THEN NOBODY DOES, and it will occur 1/11 of the time. That is not exactly what the problem calls for, since it states that the prisoner is not a jerk until he knows for certain that he will not survive, but it is a natural extension of the problem condition. So, arguably, Dej Mar's solution is not the best strategy for n = 10.
I believe that Dej Mar's solution is optimal for odd n, based on my playing with n = 11. And I have not generalized for even n. But this problem is more interesting than initially thought.
Edited on April 16, 2021, 10:30 am
re(3): solution - Follow up
