(I promised the guys in a Nadder! to post this, so here I go! Keeping my promise!)
Some time ago, Panos Papasoglu, a friend of mine, over dinner at the (highly recommended) Khukuri Nepalese restaurant in Edinburgh, told me a simple probability problem which, in his words, was the most interesting mathematical puzzle he's ever heard:
There are 100 prisoners who are sentenced to death. However, the prison's head, being merciful, offers them a possible way out: He puts 100 identical boxes, perfectly arranged in a row, in the death chamber and places the prisoner's names in them, one name per box. The prisoners wait in a room outside the death chamber. Each prisoner is asked to proceed to the death chamber and open at most 50 boxes. If he finds his name in one of them he is transferred to the mercy room where he waits. If all prisoners succeed in finding their names then they are all spared from death and are released. On the event that one of them fails to find his name in one of the 50 boxes of his choice, the process is stopped and all prisoners are immediately executed. The prisoners can talk to one another whilst in the waiting room, but, once a prisoner gets transferred to the death chamber or the mercy room, he cannot tell the others anything at all.
The question is: Can the prisoners devise a strategy to increase their chance of survival?
To see why the question makes sense, let's see what the chance is in the absence of any strategy: The chance that a prisoner will find his name is 50/100=1/2. So, if the prisoners act independently from one another, the chance that they all find their names is 1/2100 = 0.000000000000000000000000000000789. (That is, if the experiment is repeated in one thousand billion billion billion prisons then in roughly one of them the prisoners will survive.) So any strategy at all is welcome.
But is there any? What can the prisoners do? They are completely ignorant about the boxes' contents and each prisoner cannot talk to the others.
After hearing the problem, I though the same as everybody else. No way. I then went home and thought harder. I realised that, indeed, there is something that the prisoners can do. In a sense, there is one source of randomness (the random placement of names in boxes) and another one (the ordering of prisoners). If, somehow, we can couple the two (the worst we can do is keep them independent!), then, certainly, we can increase the probability of success. I thought of some schemes but none of them gave me the fantastic increase as the one presented next.
THINK IF YOU WISH ...
AND WHEN YOU ARE READY TO GIVE UP...
CLICK HERE
Some time ago, Panos Papasoglu, a friend of mine, over dinner at the (highly recommended) Khukuri Nepalese restaurant in Edinburgh, told me a simple probability problem which, in his words, was the most interesting mathematical puzzle he's ever heard:
There are 100 prisoners who are sentenced to death. However, the prison's head, being merciful, offers them a possible way out: He puts 100 identical boxes, perfectly arranged in a row, in the death chamber and places the prisoner's names in them, one name per box. The prisoners wait in a room outside the death chamber. Each prisoner is asked to proceed to the death chamber and open at most 50 boxes. If he finds his name in one of them he is transferred to the mercy room where he waits. If all prisoners succeed in finding their names then they are all spared from death and are released. On the event that one of them fails to find his name in one of the 50 boxes of his choice, the process is stopped and all prisoners are immediately executed. The prisoners can talk to one another whilst in the waiting room, but, once a prisoner gets transferred to the death chamber or the mercy room, he cannot tell the others anything at all.
The question is: Can the prisoners devise a strategy to increase their chance of survival?
To see why the question makes sense, let's see what the chance is in the absence of any strategy: The chance that a prisoner will find his name is 50/100=1/2. So, if the prisoners act independently from one another, the chance that they all find their names is 1/2100 = 0.000000000000000000000000000000789. (That is, if the experiment is repeated in one thousand billion billion billion prisons then in roughly one of them the prisoners will survive.) So any strategy at all is welcome.
But is there any? What can the prisoners do? They are completely ignorant about the boxes' contents and each prisoner cannot talk to the others.
After hearing the problem, I though the same as everybody else. No way. I then went home and thought harder. I realised that, indeed, there is something that the prisoners can do. In a sense, there is one source of randomness (the random placement of names in boxes) and another one (the ordering of prisoners). If, somehow, we can couple the two (the worst we can do is keep them independent!), then, certainly, we can increase the probability of success. I thought of some schemes but none of them gave me the fantastic increase as the one presented next.
THINK IF YOU WISH ...
AND WHEN YOU ARE READY TO GIVE UP...
CLICK HERE
Exciting! I'm glad you didn't post the answer straight away -- when I saw the problem name again I realised you can do somewhat better than 1/2^N. Let's say the first prisoner opens boxes 1-50. The 2nd prisoner is called in and they already know that the first prisoner's name is in the first 50 boxes (since they're still alive). So if the 2nd one opens any other combination (eg. 51-100) it should make the odds of success very slightly above 1/2. This is as far as my brain is getting, I'm not sure what the specific picking system should be. Ok, I'm about to click and find out...
ReplyDeleteThat's great -- it's lunchtime at work so I didn't understand the whole numerical proof (will try later) but still, very impressive. Won't say more so as not to give it away to those who haven't clicked yet!
ReplyDeleteExactly: it is easy to realise that you can do better than acting totally at random, i.e. by pre-arranging the boxes to be opened, but the point is that it is unbelievable, at first sight, that a strategy which improves chances by a factor of one thousand billion billion billion times exists!
ReplyDeleteDon't worry if you can't solve it. Many mathematicians (including myself) couldn't either.
A very nice problem. I just want to point out that the Winkler reference you give claims that the strategy has been proven to be the optimal one.
ReplyDeleteJohan: Thanks. I should be reading the references, shouldn't I? :-)
ReplyDeleteGreat problem, which I hadn't heard before! It reminds me of the hat problem: N people with randomly assigned black or white hats; each person sees all hats except her own; no communication allowed; everyone simultaneously makes a guess of BLACK, WHITE, or PASS; to win, at least one person has to guess her own hat color and no incorrect guesses may be made. Surprisingly, there is a strategy which yields success more than 50% of the time, and in fact the probability of success approaches 1 as N gets large. I'd give a link, but I couldn't immediately find a good description which didn't immediately give away the answer. Of course, I'm probably being redundant, because it already made the rounds in the math community several years ago.
ReplyDeleteIvan:
ReplyDeleteOf course, I'm probably being redundant, because it already made the rounds in the math community several years ago.
Not at all. Any good problem deserves being repeated and referenced. The one I posted here, actually, is not unknown. It circulated in the math community very very rapidly.
If you have links, please do provide them.
Peter Winkler's book Mathematical Puzzles is a good reference for the hat problem (see p. 120 for the version of it that I described).
ReplyDeleteThis problem annoys me, not because it's incorrect or not clever, but because it was the numbers that were throwing me off - almost the exact opposite of the Monty Hall problem.
ReplyDeleteIf you had said two prisoners, what's their optimal strategy, or even four, I might have been able to get the right answer but by making it 100 it threw me.
I initially thought about making sure you couldn't have 51 (or more) prisoners choosing the same boxes as that's certain death. Then about how to do better than random chance. I almost got there by assigning first person boxes 1-50, second 2-51 and so on. Almost but not quite, better than chance though.
March Hare:
ReplyDeleteYou are right to observe you can do better by a deterministic assignment of boxes to prisoners, but it is hard to imagine that there is a strategy that can do so MUCH better.
Many problems can be solved for a small number of input, by exhaustive enumeration of all possible cases, but these kind of solutions are unsatisfactory because, frequently, it's hard to see how to generalize. The reason we say 100 rather than 10 is because we do want to emphasize that one has to think using pure logic.
Now, however, you can do it not only for 100 but for 1000 or even 1 million prisoners! The mindboggling thing is that the chance for survival is about 0.3068528 for any large number of prisoners! (Imagine 1 billion prisoners. They still have 30 percent chance to survive IF they do the right thing!)
I meant I would have been able to get a better handle on the problem and head towards the right solution had the numbers been smaller. Exactly the opposite of the Monty Hall problem where the more doors there are the easier it is to see the correct solution.
ReplyDeleteThe deterministic approach is much better (than random). But even a billion times better is pathetic in this situation.
For 2 prisoners the chances are 50%, for 4, 41.67%... tending towards 30.6% as the numbers increase. Obviously real world considerations come in - the more prisoners the harder it is to remember everyone else's number 9or even your own!)
Incidentally, the log(2) approximation is wildly out for the smaller numbers (guess that's why it's an approximation :) )
I agree. The Monty Hall problem is much easier compared to this one. In the Monty Hall problem, one needs to define the problem properly and then the solution comes out easily. But this one, hm... it's really a tough cookie.
ReplyDeleteAs I said, according to the algebraist friend of mine, this is one of the best math puzzles he's ever heard.