26
$\begingroup$

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?

$\endgroup$
24
  • 2
    $\begingroup$ 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. $\endgroup$ May 5 at 14:44
  • 1
    $\begingroup$ @IvanSanchez "A correct guess leads to the immediate freedom of the guesser" $\endgroup$
    – Eric
    May 5 at 14:50
  • 1
    $\begingroup$ What happens if the bowl is full ? $\endgroup$
    – Auribouros
    May 5 at 14:56
  • 1
    $\begingroup$ 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 ? $\endgroup$
    – Auribouros
    May 5 at 14:58
  • 2
    $\begingroup$ 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) $\endgroup$
    – BmyGuest
    May 5 at 17:03

9 Answers 9

6
$\begingroup$

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

$\endgroup$
17
  • $\begingroup$ So what do they do? How should they act? $\endgroup$
    – Eric
    May 7 at 6:05
  • $\begingroup$ @Eric there is no way to act because of the paradox. $\endgroup$ May 7 at 7:15
  • $\begingroup$ 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).... $\endgroup$ May 7 at 7:15
  • $\begingroup$ ..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. $\endgroup$ May 7 at 7:24
  • 1
    $\begingroup$ 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. $\endgroup$ May 13 at 12:35
6
$\begingroup$

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.

$\endgroup$
8
  • 3
    $\begingroup$ 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. $\endgroup$
    – Retudin
    May 6 at 8:31
  • $\begingroup$ 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. $\endgroup$ May 6 at 9:14
  • 1
    $\begingroup$ 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. $\endgroup$
    – Retudin
    May 6 at 9:50
  • $\begingroup$ 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. $\endgroup$ May 6 at 15:26
  • 1
    $\begingroup$ @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. $\endgroup$ May 7 at 16:13
6
$\begingroup$

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

Decision tree

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:

Decision tree, pruned once

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:

Decision tree, pruned twice

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:

Decision tree, pruned thrice

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?

$\endgroup$
6
  • $\begingroup$ I'm not sure what your icons mean. Does the face with sunglasses mean someone who makes a correct guess? $\endgroup$ May 5 at 22:58
  • $\begingroup$ 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) $\endgroup$ May 5 at 23:19
  • $\begingroup$ β€œ 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. $\endgroup$
    – Eric
    May 6 at 1:23
  • $\begingroup$ 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. $\endgroup$
    – Eric
    May 6 at 1:44
  • 1
    $\begingroup$ 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. $\endgroup$
    – Buh Buh
    May 6 at 11:17
4
$\begingroup$

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.

$\endgroup$
8
  • 1
    $\begingroup$ +1 Brilliantly articulated! I laughed when I read "the last few prisoners get shafted..." $\endgroup$
    – JLee
    May 7 at 9:19
  • 2
    $\begingroup$ 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. $\endgroup$ May 7 at 12:46
  • 1
    $\begingroup$ @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. $\endgroup$
    – Tim C
    May 7 at 18:28
  • 1
    $\begingroup$ "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. $\endgroup$ May 7 at 21:55
  • 1
    $\begingroup$ @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.... $\endgroup$ May 8 at 23:29
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$ May 5 at 15:18
  • $\begingroup$ Oops, that above example is specifically for N=3. $\endgroup$ May 5 at 15:25
  • 1
    $\begingroup$ 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. $\endgroup$
    – Auribouros
    May 5 at 15:28
  • 2
    $\begingroup$ 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. $\endgroup$ May 5 at 15:35
  • $\begingroup$ It is stated that they're visited in order, my bad, I did change my answer to fit better $\endgroup$
    – Auribouros
    May 5 at 15:37
0
$\begingroup$

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.

$\endgroup$
2
  • 2
    $\begingroup$ 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, ... $\endgroup$
    – Hermes
    May 6 at 9:26
  • 3
    $\begingroup$ You're missing that the prisoners "would love to see others executed" $\endgroup$
    – xyldke
    May 6 at 10:01
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ "Behavior of prisoners is deterministic" Where does this follow from? $\endgroup$ Jun 28 at 16:46

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.