The 100 Prisoner's problem

[Aractus]

Here's an interesting maths puzzle...



"The director of a prison offers 100 death row prisoners, who are numbered from 1 to 100, a last chance. A room contains a cupboard with 100 drawers. The director randomly puts one prisoner's number in each closed drawer. The prisoners enter the room, one after another. Each prisoner may open and look into 50 drawers in any order. The drawers are closed again afterwards. If, during this search, every prisoner finds his number in one of the drawers, all prisoners are pardoned. If just one prisoner does not find his number, all prisoners die. Before the first prisoner enters the room, the prisoners may discuss strategy—but may not communicate once the first prisoner enters to look in the drawers. What is the prisoners' best strategy?" (Flajolet & Sedgewick 2009 as cited on Wikipedia).

To illustrate this, here is a genuinely random table of 100 numbers 1-100 numbered 1-100:


 001   002   003   004   005   006   007   008   009   010
{063} {072} {099} {092} {059} {085} {034} {087} {003} {027}

 011   012   013   014   015   016   017   018   019   020
{081} {019} {079} {025} {060} {010} {082} {070} {005} {073}

 021   022   023   024   025   026   027   028   029   030
{017} {086} {006} {018} {033} {065} {094} {008} {011} {029}

 031   032   033   034   035   036   037   038   039   040
{075} {021} {088} {100} {037} {052} {032} {093} {084} {091}

 041   042   043   044   045   046   047   048   049   050
{062} {076} {089} {071} {002} {083} {020} {035} {031} {096}

 051   052   053   054   055   056   057   058   059   060
{074} {014} {095} {077} {004} {024} {090} {066} {013} {051}

 061   062   063   064   065   066   067   068   069   070
{057} {015} {049} {038} {042} {064} {097} {040} {043} {061}

 071   072   073   074   075   076   077   078   079   080
{068} {023} {053} {007} {067} {036} {028} {045} {009} {056}

 081   082   083   084   085   086   087   088   089   090
{022} {016} {046} {080} {030} {012} {058} {069} {047} {048}

 091   092   093   094   095   096   097   098   099   100
{055} {026} {039} {098} {041} {050} {078} {054} {001} {044}

The chance of guessing right by chance alone is ½100 which in layman's terms is impossible. But there is a strategy that gives the prisoners a realistic chance of success. See if you can come up with the answer, and if not read on. Just some things to keep in mind:

The prisoners can not alter anything in the room, each time a prisoner goes in and opens drawers in a search for his number, and leaves, he is returned to cell to wait, the room is reset to how it was before he entered. No information about the numbers inside the drawers can be known or passed to the prisoners waiting to enter the room.

Obviously no matter what strategy you use the first prisoner always has a 50:50 chance of being right. So while there's no way to guarantee success, as mentioned above there is a strategy that gives them a very real chance.

---

The strategy is surprisingly simple. Simply start at your number, open the drawer, if you find your number tell the guard, otherwise use the number in the drawer to select the next drawer and repeat until your 50 guesses are used up.

Why does this strategy work?

It's simple, because doing this creates a closed cycle of numbers. Eventually you have to find your number with this method, and you will find it only once you reach the end of the loop. The cycle could be as small as one number (i.e. your number is in the drawer with your number on it), or in the worst-case there could be a cycle of all 100 numbers. But whatever the case if you start on the drawer with your number on it you are guaranteed to eventually come to a drawer with your number in it, and doing this will ignore all the numbers that aren't part of the loop. So if the biggest loop contains 50 numbers or less then the prisoners will be successful using this strategy.

Look at what happens if we use this strategy with the numbers I generated randomly above (and yes they are genuinely random and I did not change any numbers. I computed them on Stat Trek and then labelled them 1-100):

Prisoner 1 enters and has the following guesses,

1. Opens drawer 1
   
2. Opens drawer 63
   
3. Opens drawer 49
   
4. Opens drawer 31
   
5. Opens drawer 75
   
6. Opens drawer 67
   
7. Opens drawer 97
   
8. Opens drawer 78
   
9. Opens drawer 45
   
10. Opens drawer 2
    
11. Opens drawer 72
    
12. Opens drawer 23
    
13. Opens drawer 6
    
14. Opens drawer 85
    
15. Opens drawer 30
    
16. Opens drawer 29
    
17. Opens drawer 11
    
18. Opens drawer 81
    
19. Opens drawer 22
    
20. Opens drawer 86
    
21. Opens drawer 12
    
22. Opens drawer 19
    
23. Opens drawer 5
    
24. Opens drawer 59
    
25. Opens drawer 13
    
26. Opens drawer 79
    
27. Opens drawer 9
    
28. Opens drawer 3
    
29. Opens drawer 99 SUCCESS!
    

That means in this permutation of the drawers not only does this strategy work for prisoner number 1, but that it will also work for the other 28 prisoner numbers in the same cycle he just went through. There are 29 numbers in this particular loop, so for prisoners numbered 2, 3, 5, 6, 9, 11, 12, 13, 19, 22, 23, 29, 30, 31, 45, 49, 59, 63, 67, 72, 75, 78, 79, 81, 85, 86, 97, and 99 it will also take 29 guesses as they move through the same loop starting from different drawers according to their prisoner number. This just leaves 71 prisoners. Not bad. 29 correct guesses by chance would be impossible!

The next prisoner to enter that is not in this first loop of numbers is prisoner 4. So...

Prisoner 4 enters and has the following guesses,

1. Opens drawer 4
   
2. Opens drawer 92
   
3. Opens drawer 26
   
4. Opens drawer 65
   
5. Opens drawer 42
   
6. Opens drawer 76
   
7. Opens drawer 36
   
8. Opens drawer 52
   
9. Opens drawer 14
   
10. Opens drawer 25
    
11. Opens drawer 33
    
12. Opens drawer 88
    
13. Opens drawer 69
    
14. Opens drawer 43
    
15. Opens drawer 89
    
16. Opens drawer 47
    
17. Opens drawer 20
    
18. Opens drawer 73
    
19. Opens drawer 53
    
20. Opens drawer 95
    
21. Opens drawer 41
    
22. Opens drawer 62
    
23. Opens drawer 15
    
24. Opens drawer 60
    
25. Opens drawer 51
    
26. Opens drawer 74
    
27. Opens drawer 7
    
28. Opens drawer 34
    
29. Opens drawer 100
    
30. Opens drawer 44
    
31. Opens drawer 71
    
32. Opens drawer 68
    
33. Opens drawer 40
    
34. Opens drawer 91
    
35. Opens drawer 55 SUCCESS!
    

So now we have a second cycle, this time of 35 numbers. In total these two cycles will see 64 prisoners successfully find their number, and that leaves just 36 remaining. That means there now cannot be a cycle of numbers larger than 36 numbers, therefore the remaining 36 prisoners will also find their numbers without exhausting their guesses.

Prisoner 8 is the next to enter that's in neither of those number loops.

Prisoner 8 enters and has the following guesses,

1. Opens drawer 8
   
2. Opens drawer 87
   
3. Opens drawer 58
   
4. Opens drawer 66
   
5. Opens drawer 64
   
6. Opens drawer 38
   
7. Opens drawer 93
   
8. Opens drawer 39
   
9. Opens drawer 84
   
10. Opens drawer 80
    
11. Opens drawer 56
    
12. Opens drawer 24
    
13. Opens drawer 18
    
14. Opens drawer 70
    
15. Opens drawer 61
    
16. Opens drawer 57
    
17. Opens drawer 90
    
18. Opens drawer 48
    
19. Opens drawer 35
    
20. Opens drawer 37
    
21. Opens drawer 32
    
22. Opens drawer 21
    
23. Opens drawer 17
    
24. Opens drawer 82
    
25. Opens drawer 16
    
26. Opens drawer 10
    
27. Opens drawer 27
    
28. Opens drawer 94
    
29. Opens drawer 98
    
30. Opens drawer 54
    
31. Opens drawer 77
    
32. Opens drawer 28 SUCCESS!
    

Alright, that now just leaves four remaining prisoners not in one of those three large loops: 46, 50, 83, and 96. They exist in two micro loops: 46-83 and 50-96. So when those four prisoners enter and start on their numbers, they each take two guesses to find their prisoner number inside a drawer.

Here's the reason why this method gives the prisoners a chance of success:



As you can see in the graph, it all comes down to the chance of the longest cycle being 50 numbers or less. This strategy works 100% of the time when the biggest cycle is 50 or less, and fails 100% of the time when the biggest cycle is 51 or more. The actual probability for 100 prisoners is approximately 31%. So the prisoner have a 31% chance of all being pardoned if they follow this strategy, and I had a 31% chance that my random generated numbers would show an example of success as opposed to an example of failure. This strategy is so efficient that even as the number of prisoners approaches infinity they still have a greater than 30% chance of success if they follow it. For example, if this were a huge prison with 10,000 inmates, and their prisoner numbers were hidden in a bank of 10,000 drawers for them to each have 5,000 guesses at it would still give them a reasonable chance of success of 30-31%. Of course that's assuming each of them could concentrate long enough to look through 5,000 drawers without accidentally missing their number, or leaving the cycle, but human error aside it would still work.

What this puzzle demonstrates is that even a seemingly impossible problem can be solved by finding the most mathematically efficient route.

Of course in the real world things might work differently. The prison warden might have figured this out, and artificially seen to it that there's a 100-number cycle (not hard to do, you just join the smaller cycles together, for example take number 66 out of drawer 58, take number 45 out of 78, and take number 76 out of drawer 42, and then place 76 in 78, 45 in 42, and 76 in 58, and that would join all three of the large cycles in my table together). Or he might generate a new random assignment of numbers each time, which would also kill any chance the prisoner's have of successfully finding their numbers. Another thing that might happen is you get prisoners that refuse to follow the optimal plan - or those who not willing to use all 50 guesses following the plan. For example, you could have a few prisoners open 46 drawers before they decide the strategy is stupid and they're going to guess whatever they want. That's not going to affect their individual chances of selecting their numbers, but it will crush the overall chance for the team since if they leave a winning cycle of say 48 numbers early, then the fact that the other 47 prisoners who's numbers are in the cycle successfully navigated their way to their number is now irrelevant. Or you could have a smart-ass who refuses to open any drawers, or decides to break the rules in some way, also ruining it for everyone!

[BrianSoddingBoru4]

Maybe you should let other people tell you when things are interesting...

Boru

[Tiberius]

Maybe you should let other people tell you when things are interesting...

Boru

Well I for one found it very interesting. I'm always interested by probability and statistics, especially when at first it seems counter intuitive. The Monty Hall problem is a favorite of mine.

[Excited Penguin]

Maybe you should let other people tell you when things are interesting...

Boru

You owe me a keyboard.

[Tiberius]

So, if the director wanted all the inmates to die, then they would just have to create a cycle of 50 numbers, starting with the number in box #1, and ending with the number in box #50, ensuring that the number 1 does not appear in that cycle, for instance:

Box 1: 2
Box 2: 3
Box 3: 4
Box 4: 5
Box 5: 6
Box 6: 7
Box 7: 8
Box 8: 9
Box 9: 10
Box 10: 11
Box 11: 12
Box 12: 13
Box 13: 14
Box 14: 15
Box 15: 16
Box 16: 17
Box 17: 18
Box 18: 19
Box 19: 20
Box 20: 21
Box 21: 22
Box 22: 23
Box 23: 24
Box 24: 25
Box 25: 26
Box 26: 27
Box 27: 28
Box 28: 29
Box 29: 30
Box 30: 31
Box 31: 32
Box 32: 33
Box 33: 34
Box 34: 35
Box 35: 36
Box 36: 37
Box 37: 38
Box 38: 39
Box 39: 40
Box 40: 41
Box 41: 42
Box 42: 43
Box 43: 44
Box 44: 45
Box 45: 46
Box 46: 47
Box 47: 48
Box 48: 49
Box 49: 50
Box 50: 51

In fact if the director put the numbers in the boxes following this pattern (the number in the box is the number of the box plus 1, and the number in box 100 is 1) then he would guarantee that the first prisoner would not find their number, even if the first prisoner was chosen at random.

[FebruaryOfReason]

Fascinating - thank god you're on team Atheist, Aractus!

Have you read "Inevitable Illusions: How Mistakes of Reason Rule Our Minds" by Massimo Piattelli-Palmarini?
http://www.amazon.com/Inevitable-Illusio...047115962X

Highly recommended, but not light bedtime reading!

[Excited Penguin]

I used to like mathematical puzzles, but I remember not being able to explain how I arrived at the answers and so the teachers sometimes thought I was cheating.

[BrianSoddingBoru4]

Here's the correct solution (remember, this is a prison): Joey 'Little Foots' Gambinocolumbocapone has friends on the outside. He makes it plain to the prison director that if he (Joey) doesn't pick his own number, terrible things will happen to the director's family ('We don't want nobody should get hurt or nuttin, do we?'). Problem solved.

Boru

[Cecelia]

In fact if the director put the numbers in the boxes following this pattern (the number in the box is the number of the box plus 1, and the number in box 100 is 1) then he would guarantee that the first prisoner would not find their number, even if the first prisoner was chosen at random.

By the 20th time though, most prisoners would recognize the pattern.   It'd be a good test though.

[Aoi Magi]

In fact if the director put the numbers in the boxes following this pattern (the number in the box is the number of the box plus 1, and the number in box 100 is 1) then he would guarantee that the first prisoner would not find their number, even if the first prisoner was chosen at random.

By the 20th time though, most prisoners would recognize the pattern.   It'd be a good test though.

But a prisoner wouldn't know what the others chose or what pattern they saw. In this case the prison warden has a much higher chance of detecting what pattern the prisoners are using than the other way around.