N prisoners locked in cells

Question

N prisoners are locked in N separate cells, numbered 1 to N. The warden visits each cell in order with a bowl. Each prisoner can decide whether to put a single coin in the bowl, depending on its current content. After collecting from the Nth cell, if the bowl is empty, the game ends and nothing happens (the prisoners continue to serve their sentence). Otherwise, the warden shows his bowl to the prisoners who haven't contributed any coins. These prisoners can guess from which cells those coins are, with the following consequences:

1. A wrong guess leads to the immediate execution of the guesser.
2. A correct guess leads to immediate freedom of the guesser, and the execution of all coin-givers.
3. If they refuse to guess, they just continue to serve their sentence in the prison.
4. If there's no correct guess, all coin-givers will be freed.

All coins are identical. All prisoners prefer life to freedom, and freedom to imprisonment, and will choose to guess if and only if they're 100% sure (they don't take chances with their own lives, but would love to see others executed). Each prisoner knows his cell number and is locked in his cell throughout the game. There's no information exchange of any kind between prisoners. All the above are common knowledge.

Question: How many prisoners will be freed?

Answer 1

There is a certain paradox.

• If all prisoners are considered to make a perfectly logical (fixed) choice.

  Say that the perfect choice for the first $N-1$ prisoners contains for some of those prisoners the choice to add a coin to the bowl, then the $N$-th prisoner will know all of this as well and that prisoner can choose to not add a coin to the bowl. That prisoner will be able to get free by guessing all the coins correct. But it will do so by sending all those prisoners that added a coin to death. So this can not be a solution.

  Therefore, the only option is that none of the prisoners add a coin into the bowl.

• If some prisoners are not considered to make a perfectly logical (fixed) choice.

  However, knowing that the perfect choice for all of the prisoners is to add no coin to the bowl, it becomes a good choice to add a coin into the bowl. So a prisoner might decide to add a coin to the bowl without the others knowing who did it.

This paradox arises because we try to solve the puzzle by assuming that all the prisoners are acting in a 'perfect logical way'. However, there is no perfect logical way.

The paradox also arises because we assume that there is a solution. But, there may not need to be a solution. There is no Pareto optimum. If we assume a certain optimal strategy for all N players, then this will change the strategy by the other players (who, being perfect logicians, will be able to assume this as well), but this change will again change the strategy and so on. A simpler puzzle that shows this effect is like: "A is prefered over B, B is prefered over C, C is prefered over A. What option among A, B or C is chosen?".

Answer 2

Well, cases for N=1, 2 and 3 are trivial and no need to spoiler them.

1. prisoner gives coin, gets out.
2. neither gives coin as the other trivially executes him.
3. if the first or the last gave coin, second would know who put all the coins in. He won't put the coin in himself in that case, because he can (and will) opt to execute them instead. So, first and last cannot give coins. Being master logicians, second knows that he cannot put coin in either, otherwise first and last would know who did it (as they know they can't be the ones giving coins in).

Fun starts with N=4 and so do spoilers

The first prisoner knows that giving coin in would let 2nd identify him. It seems obvious he cannot put the coin in. But this obviousness is incorrect - if the first prisoner knows someone else also puts a coin in, second prisoner might not be able to identify all coins correctly, letting the first escape. Let's first assume first did put coin in.

Now

2nd prisoner cannot put the coin in. Third prisoner would immediately know who put the coins in, so won't put the coin in. Third prisoner sees 1 coin inside, so he can put the coin in. 4th prisoner won't be able to know if the coins come from 1 and 3 or 2 and 3 (he does know they don't come from 1 and 2). 4th prisoner cannot put the coin in. He knows that the only prisoner that didn't put the coin in now sees N-1 coins and simply names everyone else for killing and walks out.

But this seems all wrong

If first always puts the coin in, as does third, then obviously 2nd and 4th know exactly who did it and execute them. However, a tiny change makes this approach look somewhat feasible - first prisoner puts coin in with some probability p1. IF the second prisoner sees the coin, he cannot put it in, as in above. But if he doesn't, he puts his own coin in as he knows he cannot be distinguished from 1 by prisoners 3 and 4, or know whether 3 or 4 put the coin in (by 1). Likewise, prisoner 3 puts coin in with some probability p3. Prisoner 4 then puts the coin in for that final case, yes prisoner 3 knows he did it, but he doesn't know whether 1 or 2 dropped the coin.

What about N=5?

1 and 2 can both put coins in, third cannot, 4th can and 5th again cannot. This time we have p1, p2 and p4, with additional constraint that if first didn't put the coin in, second ignores his probability p2 and puts the coin in. This time, either p1 or p2 can be 1 (but not both), and p4 cannot be 1. Because they are greedy bastards, p1 is 1 and they all know it.

Finally, generalization

Prisoners 1 to N-3 can put coins in. N-2 cannot, N-1 can and N cannot. They put coins in with some probabilities between 0 and 1 (excluding these two values for N-3 and N-1, including 1 for others), additionally with constraint that if any of previously potential people didn't put coins in, they can safely - likewise N-2 and N can put coins in, if a coin is missing from the count.

Therefore

N-2 prisoners walk out in N=4 and above. The worst case for prisoners is N=3 where all remain in prison.

Answer 3

I've decide to brute-force a decision tree for $N=4$, and see if and what patterns emerge:

In the outcomes, "😑" stands for "still in jail", "💀" stands for "dead" and "😎" stands for "getting out of jail". "🪙" is putting a coin, "◯" is not putting a coin, and "❌" is "it's not been my turn to make a decision yet".

Note that there are two states in which a prisoner makes a correct guess even when faced with apparent incomplete information - this is because there is only one game state where they see the particular combination of "coins seen at decision time" and "coins seen at guess time". Those are noted as $(n/m)$ in the decision tree.

(I'm assuming that a correct guess ends the game prematurely, preventing any further prisoners from making guesses. Not making this assumption does not change the conclusion, as far as I can tell.)

Now I shall prune the decision tree, starting with 4. Since 4 has limited information (the number of coins visible when making the decision), the pruning must be the same for all branches sprouting from states which have the same information available to 4.

There is one branch for 0 and 3 coins - easy to prune. But there are several branches for 1 and 2 coins; the outcomes "going free" and "die" are both possible if 4 puts up a coin in some branch. Since the strategy is to avoid the worst outcome, 4 will not put a coin when faced with that information.

So the tree is left as:

Let's prune the decisions of 3, using the same reasoning. 3 might see 0, 1 or 2 coins when making the decision.

For 2 coins, putting one more leads to death. But for 0 or 1 coins, putting one more always leads to sweet freedom, even though 1 coin appears in two branches.

After the second pruning, the tree is:

Same with the decisions of 2. Which is easy since 2 faces a simplified tree where we need no grouping of states where the prisoner sees the same information.

Putting a coin might lead to death, not putting one doesn't.

So after the third pruning:

The decision of 1 is then trivial.

I will therefore conclude that

For even values of $N$, half of the prisoners go free: those in even cell numbers.

But... wait a second. What if....

Prisoners 2 and 4 were absolutely sure that all other prisoners are perfectly rational and use a defensive strategy? In that case, the outcome for coin distribution 🪙◯🪙◯ is not 😎😑😎😑, but rather 💀😎💀😎. Does that change the pruning?

Answer 4

There is at least one equilibrium where even with perfect knowledge of every other prisoner's strategy, no prisoner can improve their odds of survival or escape by changing strategies.

At one such equilibrium:

98 prisoners go free, 2 remain imprisoned, 0 die.

I will show how I get there by starting at a naive strategy for all prisoners, and then choosing one prisoner at a time to improve their outcome by changing strategies. (Or skip to the final timeline if you just want to see the strategies).

The first timeline

The prisoners first consider a narrow-minded induction strategy, reminiscent of the Unexpected Hanging Paradox.

Prisoner 1 sees and empty bowl, and would never put a coin in because prisoner 2 will know, guess correctly, and kill them. Thus, prisoner 1 can be ignored. Prisoner 2 can't put a coin in because prisoner 3 would see it, know that prisoner 1 didn't put it there, and so guess correctly and kill them... By induction, prisoner N<100 sees an empty bowl, and would never put a coin in, because if they did then prisoner N+1 would know that prisoners [1, N-1] couldn't have put it there, guess N, and kill them.

Until the base case

Prisoner 100 sees an empty bowl, and would never put a coin in, because prisoner 99 would know that an empty bowl passed them, therefore prisoner 100 is the only one who could have put the coin in. Prisoner 99 would guess correctly and kill them.

In this timeline, no prisoners go free.

The second timeline

Prisoner 1 deduces that the above would happen. They prefer freedom to imprisonment, so they make a different choice.

Suppose prisoner 1 puts a coin in anyway. Prisoner 2 sees this and wonders if perhaps Prisoner 1 was not such a perfect logician, or she did not prefer life to death, or she had some doubts about prisoner 2's deductive prowess. Thinking his freedom assured, Prisoner 2 passes the bowl, planning to rat out Prisoner 1 and win his freedom.

Then,

Prisoner 3 receives the bowl. She does not know which of the two prisoners before her put a coin in. Since Prisoner 4 won't be able to deduce the answer either, prisoner 3 knows that she can safely put a coin in and go free. And so on until prisoner 100. Prisoner 100 knows that if he puts a coin in, then whomever did not put a coin in would see 99 coins. Wanting to avoid this, he does not put a coin in.

On to the guessing phase

Prisoner 2 sees 98 coins. He knows that if prisoner 100 had received a bowl with 98 coins, they would be obligated to pass. So he is about to make his guess but... he can't. He's not sure. Any of prisoners [3, 99] could have deduced that he would make that guess, and therefore passed, allowing prisoner 100 to put the coin in. Prisoner 100 cannot guess either. He remains in prison.

And so

All prisoners except 2 and 100 go free. Nobody dies.

...But wait!

The third timeline?

Prisoner 2 deduces the above timeline. Preferring freedom to imprisonment, he considers an alternative.

He puts a coin in. Or he imagines that he might do so. What if he did? Then, Prisoner 3 would see the same situation as he did in the second timeline. Since prisoner 3 also knows how that timeline ends up, they'd put a coin in to avoid imprisonment, and so on, until prisoner 99. Prisoner 99 knows that if she puts a coin in, then Prisoner 100 will see 99 coins and kill them all. So she passes. Prisoner 100 also passes for the same reason as timeline 2. Then prisoner 99 correctly names prisoners 1-98 as the coin-placers, kills everyone, and goes free.

When the dust settles

98 prisoners are dead, one goes free, and one remains imprisoned.

The fourth timeline

Prisoner 98 sees the impending calamity, and moves to prevent it.

He passes. Prisoner 99 sees the same situation as the second timeline, puts a coin in, and goes free.

The fifth timeline

With all prisoners aware of all of the above possibilities, random strategies begin to emerge.

The default strategy for all prisoners is to place a coin if there are at least two coins missing from the bowl, otherwise, choose randomly.

The last few prisoners get shafted by a couple extra restrictions.

Prisoner 98 must pass if there are no coins missing. Prisoner 100 must pass if there is only one coin missing.

Using these strategies

All prisoners who place coins go free, because neither of the two who do not place coins can deduce who the other non-placer is.

The final timeline

Some prisoners can improve their odds.

Prisoners [1, 96]

Can put the coins in and be guaranteed freedom

Prisoner 97

Wants to always put a coin in, but if prisoners 99 and 100 know that she always puts a coin in, she'll die. So she sticks with the random strategy to be safe (they're "perfect logicians," so they would be able to predict her change of strategy if she were the sort of person to do that). So she chooses a random weight that assigns an arbitrarily low, but still non-zero, probability to passing.

Prisoner 98

does the opposite of whatever 97 did.

Prisoner 99

Wants to always put a coin in, but if whichever of 97 or 98 who didn't put a coin in before can be certain she did so, she will die. She plays random for the same reason that 97 did, and in the same way.

Prisoner 100

Does the opposite of whatever 99 did.

At this point, no prisoner can improve their outcome.

Answer 5

Case N=3. 1 coin appears. Prisoner 1 and prisoner 3 think "it has to be 2, because the other knows that if he puts a coin, he dies. But 2 knows that we will deduce this, so he can't have put in the coin either. But he knows that the doubt would arise and we would not guess, so it has to be his. But he knows we'd think this, so it can't be his." He hesitates, so he doesn't risk his life and doesn't guess, so 2 is saved.

With this case we see that when both 1. putting in a coin and 2. making a guess, they are not going to take a risk. When putting in a coin you can force a deduction loop. When the others guess, they will always take the safe option.

Thus, for any N > 3:

If prisoner N receives N-2 coins (that is, his and another one are missing), he will not be able to deduce who they are from, since, if he could, the others would have deduced that he would deduce it and they would not have put in a coin; much more if even fewer coins arrive.

If prisoner N-1 receives less than N-2 coins (that is, all of them up to him) he will not be able to deduce anything either with 100% certainty.

In general, for each prisoner, it is impossible to know anything if all or none of the coins before him are in the bucket, and all or none after him are too.

Therefore, everyone will put in coins up to prisoner N-2, which, if he puts in his coin, he is giving prisoner N-1 an "all before and all or none after". Prisoner N-1 will put coin, since he cannot trigger the situation for N, and N will not put coin, since it would trigger the situation for N-2 (although he would not be sure who the situation would be for; really, he only knows that it would be generated), and N-2 prisoners will be released, because neither prisoner N-2 nor prisoner N could secure anything.

Answer 6

Let's try this, first with $N=1$

The prisoner will simply have to put a coin in the bowl, as per the rules of the game, any prisoner who hasn't put a coin has to guess, and if no guesses are correct, then all coin-givers are freed. In that case, the single prisoner is freed.

Now, what about $N=2$ ?

Once a first prisoner puts money in the bowl, the second one will see that there is money in the bowl, and would rather escape AND kill the other fellow inmate than simply have both of them escape. Which he will do by guessing the coin's owner correctly, and escaping, leaving the other inmate's corpse in his path.

Now for a general formula for $N$

The first inmate will put a coin inside, the second inmate, seeing the coin, will know the coin was placed by inmate 1. So he will choose to kill inmate 1, and escape.
The third inmate, thinking like a perfect logician, will do the same, and choose to kill inmate 1, and so on until inmate $N$.

However, if prisoner 3 doesn't think like a perfect logician (which is a fair assumption), he would think that either 1 or 2 placed that coin, and because he is unsure as to who did so, he will place another coin, hoping to escape. This will go on to prisoner $N$, who will place the $N-1^{th}$ coin in the bowl. Prisoner 2 will have to guess, or rather, will choose not to, and all the other prisoners will be able to leave.

Conclusion:

The worst outcome is for $N=2$, where we have 1 escaped and 1 dead. Otherwise everyone can escape, except for Prisoner 2, who will think greedily, wanting to kill Prisoner 1 instead of escaping with them.

Answer 7

I think that to be 100% sure everyone will put in a coin, so in the case that guessing time appears, they will say an illogical number because only they know their own cell number. That leads to a bad guess and "If there's no correct guess, all coin-givers will be freed.". That means if everyone puts in a coin, everyone will be free. That will happen if everyone put a coin, but, Who will guess?

"if the bowl is empty, the game ends and nothing happens (the prisoners continue to serve their sentence). Otherwise, the warden shows his bowl to the prisoners who haven't contributed any coins. These prisoners can guess from which cells those coins are"

I'm not a native English speaker, so I think I am misunderstanding something.

Answer 8

This is fun - it opens up all kinds of fun discussion but the fact that this is done in two phases makes only one answer work.

They are offered the opportunity to decide if they're going to want to guess before all information is in so there will never be certainty.

They all place a coin in the bowl because they will only guess if they're 100% certain. You can only guess if you didn't put a coin in the bowl With no guesses, there are no correct guesses, even if one is a subset of the other. With zero correct guesses, N prisoners go home. There's the question of the Nth prisoner, however, they also have no information when asked for a coin. Yes, if they decided not to, they'd be able to go home and leave everyone dead - but, by the rules, they haven't seen the bowl yet so they place a coin in because they aren't 100% sure.

Let's reverse the first question asked - "If you're not 100% sure you know what everyone else is going to do, place a coin in the bowl."

Answer 9

I'm interpreting "they don't take chances with their own lives, but would love to see others executed" as "prisoners prefer to obtain freedom by guessing who put their coin in the bowl rather than obtaining freedom by putting a coin in the bowl".

I think the reasoning becomes straightforward if you assume that all prisoners are perfect logic machines. I say "machines", not "human logicians" because of additional limitation: they can't generate random numbers (i.e. their behaviour is deterministic).

The reasoning goes as follows:

1. Staying alive is preferable to death, so: if a prisoner X is able to deduce that some other prisoner would deduce names of prisoners which put their coins in the bowl, then the prisoner X wouldn't put a coin in the bowl

2. Behavior of prisoners is deterministic, so: every prisoner knows what other prisoners would do, including who would put a coin in the bowl

3. Observations 1. and 2. imply that putting a coin in the bowl always means death, so it is never recommended by a perfect logic machine.

Answer: For N >= 2, nobody would put their coin in the bowl and nobody would be freed