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:

A wrong guess leads to the immediate execution of the guesser.
A correct guess leads to immediate freedom of the guesser, and the execution of all coin-givers.
If they refuse to guess, they just continue to serve their sentence in the prison.
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?

I'm confused about the preferences of the prisoners. Assuming N=2 and 1 putting a coin, what would 2 prefer?: (a) not put a coin, guess correctly, kill 1 and stay locked, or (b) put a coin, trigger "if there's no correct guess, all coin-givers will be freed" (since there have been no guessers), and go free. — IvanSanchez, May 05 '22 at 14:44
@IvanSanchez "A correct guess leads to the immediate freedom of the guesser" — Eric, May 05 '22 at 14:50
What happens when all the prisoners put coins inside the bowl, there can't be any guessing party, so they should all go free, right ? — Auribouros, May 05 '22 at 14:58
What happens if multiple guessers could guess correctly? Does just the first one to guess go free? — GoblinGuide, May 05 '22 at 15:13
Just to be sure: A guess means, assigning each coin to cell-number, i.e. if there are 3 coins in the bowl one would have to guess which 3 cell(inmates) did contribute. (As opposed to guess a single person correctly who contributed a coin) — BmyGuest, May 05 '22 at 17:03
Own freedom, death of x > own freedom, death of x-1 > own freedom, jail of x > own freedom, jail of x-1 > own freedom, freedom of x > own freedom, freedom of x-1 > own prison, death of x > own prison, death of x-1 > own jail, jail of x > own jail, jail of x-1 > own prison, freedom from x > own prison, freedom from x-1 > own death, death of x > own death, death of x-1 > own death, jail of x > own death, jail of x-1 > own death, freedom of x > own death, freedom of x-1? — Hermes, May 06 '22 at 11:39
Is there a particular order in which the prisoners can guess? Do the prisoners know N? — Sextus Empiricus, May 06 '22 at 15:22
@SextusEmpiricus They know N and all the rules of the game. The guess part happens after the warden has asked the the Nth cell for coin, so the order in which the prisoners guess doesn't matter. — Eric, May 06 '22 at 15:28
Do you get free by a single identification or do you need to identify all coins? — Sextus Empiricus, May 06 '22 at 15:34
@SextusEmpiricus That's already answered above. They need to identify all coins — Buh Buh, May 06 '22 at 15:38
"All prisoners prefer life to freedom" - I guess, this is supposed to be "All prisoners prefer life to death"? — Jonathan Scholbach, May 06 '22 at 20:58
@jonathan.scholbach Yeah, that statement is kind of redundant, because a prisoner can't be both free and dead. — Eric, May 06 '22 at 22:55
"All the above are common knowledge" - I guess, the fact that this is common knowledge is also common knowledge? (and so on until infinity) — Jonathan Scholbach, May 07 '22 at 01:10
If a prisoner can decide between being free and have everyone being killed and having everyone being freed, what would they prefer? — Helena, May 08 '22 at 12:21
@Auribouros , you had asked , "what happens if the bowl is full" . This will never happen . Think of it this way. If the first n-1 people have all put in a coin then the nth person would choose not to put in a coin. Once the putting in coin round is over, the warden will show the bowl to the nth prisoner. The nth prisoner will know that the n-1 coins come from the first n-1 prisoners. He will say this and get free . — Hemant Agarwal, May 08 '22 at 23:19
Having seen so many of this type of puzzle, I have to ask: If all the prisoners are perfect logicians, how did they end up in prison? (The "would love to see others executed" line makes it less likely they've been unfairly imprisoned) — Joel Rondeau, May 11 '22 at 05:28

Sextus Empiricus · Accepted Answer · 2022-05-07T22:03:17.537

7

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?".

edited May 07 '22 at 22:03

answered May 06 '22 at 18:35

Sextus Empiricus

206
1
6

So what do they do? How should they act? – Eric May 07 '22 at 06:05
@Eric there is no way to act because of the paradox. – Sextus Empiricus May 07 '22 at 07:15
They might act irrational and place a coin. Except the n-2 prisoner, because a full bowl will tell the n-1 prisoner that all before him placed coins and the one behind him he can deduce based on the final number. So the n-2 prisoner has to prevent a full bowl at that point. The n th prisoner can neither place a coin, because he has to prevent that in the end there will be n-1 coins in the bowl (which means that the prisoner that did not place can guess all the others).... – Sextus Empiricus May 07 '22 at 07:15
..but the problem is how we interpret "will choose to guess if and only if they're 100% sure". In this situation where n-2 did not place a coin, the n-1 prisoner might deduce that it must have been n-2 in front of him that had to place the coin. But then n-1 must assume that all the n-3 prisoners before that are greedy and placed a coin. However that would make them get killed if they know that n-1 prisoner knows this. And acting like that, getting yourself killed, is against the rule so n-1 can not be 100% sure and n-1 can't make the guess that n-2 has to be the one that did not place a coin. – Sextus Empiricus May 07 '22 at 07:24
“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”
You can't say it's a good choice to add a coin into the bowl, because you don't know what the others will do when they see coins in the bowl. All we can say is, if one puts a coin in the bowl, we simply go back to the previous case ("Say that the perfect choice for the first −1 prisoners contains for some of those prisoners the choice to add a coin to the bowl...")
– Eric May 08 '22 at 10:05
@Eric and that is the paradox about it. – Sextus Empiricus May 08 '22 at 11:07
No, that only says under the assumption of perfectly logical (fixed) play, no one should put a coin. – Eric May 08 '22 at 11:11
@Eric the conclusion that nobody puts a coin is only arrived at by means of contradiction. It is not a solid proof. It still has the option that 'nobody putting in a coin' is also an option that is not stable and would allow prisoners to improve their result. And indeed if 'nobody putting in a coin' would be the best solution that all prisoners logically deduce, then a prisoner can decide to put in a coin after all (which again changes the logical deduction by the others, so this can go forever). The error in the proof by contradiction is the implied assumption that there has to be a solution. – Sextus Empiricus May 08 '22 at 11:37
@SextusEmpiricus in the case of N=3, if you as prisoner #3, who didn't put a coin, see one coin in the bowl, who would you guess, and why? – justhalf May 10 '22 at 05:26
@justhalf It makes no sense that there is a coin in the N=3 case, so prisoner #3 can't be sure who did it and shouldn't guess. – Sextus Empiricus May 10 '22 at 10:36
Precisely. So, #2 can put a coin and #3 will behave like you said, and be freed. – justhalf May 13 '22 at 11:59
@justhalf yes, #2 can put a coin in and the solution that nobody puts a coin in is not an equilibrium. Given that the others do not put a coin in #2 can change the decision to put a coin in. – Sextus Empiricus May 13 '22 at 12:05
But it gets paradoxical again. If #2 has the best strategy to put a coin in then it becomes again logical for #2 to put a coin in and #3 might be able to deduce that it should have been #2. So in the N=3 case the result that none put a coin in might be the best strategy. It depends on how you interpret the rule that #3 needs to be certain about their guess. If #3 can be 100% certain that #1 will never ever put a coin in (because that would be a certain kill) then any potential coin must be from #2. – Sextus Empiricus May 13 '22 at 12:19
1

Actually, while it is paradoxical, there is actually a Nash equilibrium for the case N=3 (but, the equilibrium won't be able to be obtained if the prisoners lack information about arbitrary choices). If the strategy is for nobody to put a coin, #2 will trivially be able to guess the others when these others put a coin in and #3 will have the strategy to guess #2 if they would put a coin in, then nobody can make an improvement in their stategy by putting a coin in. – Sextus Empiricus May 13 '22 at 12:35
Yep. So the Nash equilibrium is that #2 won't put a coin. Which is the conclusion other answers have as well. Nice one. – justhalf May 17 '22 at 03:19
@justhalf but it fails when N>3. (Also, a Nash equilibrium may not need to be obtained. What if there are multiple of such equilibria?) – Sextus Empiricus May 17 '22 at 05:02
I was just discussing about N=3, so we're good. =) As for multiple equilibria, it's clear for N=3 that no coins is the only one. – justhalf May 17 '22 at 06:51

score 6 · Answer 2 · edited May 09 '22 at 14:10

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?

I'm not sure what your icons mean. Does the face with sunglasses mean someone who makes a correct guess? — reallydismayed, May 05 '22 at 22:58
Sunglasses means "get out of jail" (by either not putting a coin and guessing correctly, or by putting a coin and then nobody being able to make a sure guess) — IvanSanchez, May 05 '22 at 23:19
“ In that case, the outcome for coin distribution ◯◯ is not , but rather ” Prisoner 2 will not be executed in this case, because he can always refuse to guess. — Eric, May 06 '22 at 01:23
If you have contributed a coin, you either get free or get executed in the end. So I believe the 10th branch is also incorrect. — Eric, May 06 '22 at 01:44
The pruning logic is not sound. E.g. Player 4 should not be able to differentiate between ◯◯ and ◯◯. These two states should result in the same decision for Player 4. — Buh Buh, May 06 '22 at 11:17
Yeah, @BuhBuh was right, and consequently I've rewritten the whole thing. The conclusion, however, remains the same. — IvanSanchez, May 06 '22 at 17:05

score 6 · Answer 3 · answered May 06 '22 at 07:51

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

prisoner gives coin, gets out.
neither gives coin as the other trivially executes him.
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.

I think 4+ is spot on. I disagree 3 is trivial though. Though 3 knows 1 did not put the coin in (since 2 would kill 1), 3 also knows 2 would not put the coin is, since 3 (and also 1) would accuse and thus kill 2 (according to your reasoning). My conclusion is that 2 can put a coin in, since both others do not now for sure who made the suicidal move, and thus stay silent. — Retudin, May 06 '22 at 08:31
The trick with 4+ is in probability. With 3, probability of first or third prisoner putting coin in is 0 because he guarantees his death with the move and won't do it. Therefore, if third or first see a coin in, they both know it is prisoner 2 putting the coin in. — Zizy Archer, May 06 '22 at 09:14
I understand that that is what makes 4+ clearly correct, but the paradox of 'three prisoners with 1 coin at the end' is that 1 and 3 also 'know' that 2 would not make a suicidal move; so the reasoning "1 would not make a suicidal move, so 2 did." does not make sense. Only prisoner 2 can make a guess with absolute certainty, if he is not the one that put the coin in the bowl. — Retudin, May 06 '22 at 09:50
I don't think the situation of #2 placing a coin for N=3 can ever happen given the puzzle rules. The very fact that placing a coin is suicidal for #2 is what makes it not suicidal, which since placing a coin is only not suicidal for #2 makes it suicidal again. #2 should look at this and reason that some of the time they die, and some of the time they don't and not place a coin. — GoblinGuide, May 06 '22 at 15:26
A problem here is that instead of using some probability $p_k < 1$ any $k$-th prisoner can also choose to add the coin with probability $p_k = 1$. There is no way that the other prisoners can tell whether the coin has been placed based in probability or not. — Sextus Empiricus, May 06 '22 at 18:50
@Retudin I see the paradox here now, thanks. It is immediately obvious 2nd cannot put coin in as others could identify him, so if he still did, 1st and 3rd would get confused as it isn't a logical move and wouldn't guess then. But I believe that as there is NO reasoning for 1st or 3rd prisoner ever putting a coin in (it is guaranteed death by prisoner 2), prisoners 1 and 3 would still guess it was prisoner 2 doing the paradox - which is what prevents prisoner 2 from going for this paradox. — Zizy Archer, May 07 '22 at 16:13
@SextusEmpiricus Well, in case of 4 prisoners, you can't have P1 or P3 always putting the coin in. Probability can be arbitrarily close to 1 but if it is exactly 1, other prisoners can identify P1 and P3 as the ones putting the coins in. — Zizy Archer, May 07 '22 at 16:14
@ZizyArcher the others will not know which probability is used, so it can be equal to 1. — Sextus Empiricus, May 07 '22 at 18:26

score 4 · Answer 4 · answered May 07 '22 at 06:57

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.

+1 Brilliantly articulated! I laughed when I read "the last few prisoners get shafted..." — JLee, May 07 '22 at 09:19
The problem is that perfect logician does not mean the same as a person that has 100% fair play. The 97-th prisoner could add a coin based on some probability, say the flip of a coin or rolling a dice, but if the result is in their disadvantage then they can easily choose to flip or roll again (who would know?). It is not in the advantage of the 97-th prisoner to play fair. Differently said, the problem here is that there is not a Pareto optimal solution. Player 97 is not gonna play nice and use a probability to decide whether or not to add a coin into the bowl. That is not in their advantage. — Sextus Empiricus, May 07 '22 at 12:46
@SextusEmpiricus - I'm taking "perfect logicians" to imply that all players can fully deduce another prisoner's strategy - since they're all perfect logicians, they just have to imagine what they would do in that situation. Since Prisoner 97 knows that Prisoner 99 a perfect logician (and also that prisoner 99 won't guess unless 100% sure), prisoner 97 must choose a strategy that has a nonzero chance of passing. Otherwise, death. — Tim C, May 07 '22 at 18:28
Talking about "internal state of mind" of prisoner 97 is introducing confusion here. Prisoners do not communicate about their strategy, and it seems you want to introduce some telepathy here. I think, this confusion can be revealed by the question: What probability is 97 going to choose? If I see it correctly, there is no non-contradictory answer to that. — Jonathan Scholbach, May 07 '22 at 20:09
"perfect logicians" implies that all players can fully deduce another prisoner's strategy, unless it is not possible to deduce another prisoner's strategy. Being a perfect logician does not mean that there is a perfect logical answer or that one can deduce the choices made by others with certainty. The solution where prisoner 97 or others as well have to use probability is a fallacious circular argument. Prisoner 97 is not necessarily gonna use probability in order to make prisoner 99 unable to guess. Prisoner 99 will not be able to verify what prisoner 97 did, so prisoner 97 can cheat. — Sextus Empiricus, May 07 '22 at 21:55
I think in a game like this, having all players be fully aware of the other players' strategies is the only meaningful definition of perfect logician. They can deduce what the optimal strategy would be to play in that position, and assume that they're playing it. Prisoner 97 can cheat, but if prisoner 97 was the kind of person who would cheat 100% of the time, Prisoners 99 and 100 would be able to deduce with certainty that they put a coin in. Thus, in order to survive, Prisoner 97 must be the kind of person who would not cheat (or at least not cheat 100% of the time). — Tim C, May 08 '22 at 18:02
@TimC in that kind of situation prisoners 97-100 have some probability to stay in prison which is not optimal. Therefore they could also decide that all put a coin in, which means that all 100 get out of prison. They all put a coin in even the prisoner 100 when it sees 99 coins in the bowl and has the ability to kill the others. According to your way of reasoning prisoner 100 would not kill the 99 others because if the others knew that prisoner 100 would do that then they would not play that strategy and prisoner 100 has to play with the probability.... — Sextus Empiricus, May 08 '22 at 23:29
.... The problem with that is that the prisoners, being perfect logicians, do not need to come up with that optimal solution. The prisoner 100 has to decide to not go after their best option in order to reach a better state for the entire group. In this case it becomes like the other prisoners dilemma. The problem is that the prisoners need to collaborate, but they do not know whether the others will collaborate. There is no logical rule to decide that. — Sextus Empiricus, May 08 '22 at 23:35

score 2 · Answer 5 · edited May 07 '22 at 09:07

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.

Auribouros · Answer 6 · 2022-05-05T15:36:42.907

0

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.

edited May 05 '22 at 15:36

answered May 05 '22 at 15:10

Auribouros

6,581
11
48

I don't think your general case is correct. The prisoners know the contents of the bowl when they choose to add a coin or not, as well as their order so if inmate 1 or 3 places a coin inmate 2 will always know who placed that coin. – GoblinGuide May 05 '22 at 15:18
Oops, that above example is specifically for N=3. – GoblinGuide May 05 '22 at 15:25
1

Considering all prisoners as perfect logicians, they would put a coin in their best interest. I do, however, understand your reasoning, and will edit my post as such. – Auribouros May 05 '22 at 15:28
2

I feel like it's implied in the OP that the prisoners know that the warden visits them in order, but fair point, it's not explicitly stated. Regardless, you can never have N prisoners escaping (except when N=1). If prisoner N gets the bowl with N-1 coins they will not place a coin and instead execute everyone else to escape. – GoblinGuide May 05 '22 at 15:35
It is stated that they're visited in order, my bad, I did change my answer to fit better – Auribouros May 05 '22 at 15:37
@GoblinGuide Yes, they know that, and in order simply means 1,2,3,...,N. – Eric May 05 '22 at 15:48

score 0 · Answer 7 · edited May 07 '22 at 09:07

0

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.

edited May 07 '22 at 09:07

JLee

18,202
2
55
172

answered May 06 '22 at 08:16

Ekaitz Martin

1

2

The N would not put coin, he would go free and all the others would die. To avoid this, the N-1 would not put a coin, which would make the N not put a coin either, so the N-1 would go free and all the previous ones would die, ... – Hermes May 06 '22 at 09:26
3

You're missing that the prisoners "would love to see others executed" – xyldke May 06 '22 at 10:01

senecaTheMeek · Answer 8 · 2022-05-09T15:30:49.030

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."

score 0 · Answer 9 · answered Jun 28 '22 at 16:14

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

"Behavior of prisoners is deterministic" Where does this follow from? — Sextus Empiricus, Jun 28 '22 at 16:46