Our server costs ~$56 per month to run. Please consider donating or becoming a Patron to help keep the site running. Help us gain new members by following us on Twitter and liking our page on Facebook!
Current time: March 28, 2024, 12:38 pm

Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
The 100 Prisoner's problem
#1
Question 
The 100 Prisoner's problem
Here's an interesting maths puzzle...

[Image: mVOShuq.png]

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

[Image: gwici4K.png]

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!
For Religion & Health see:[/b][/size] Williams & Sternthal. (2007). Spirituality, religion and health: Evidence and research directions. Med. J. Aust., 186(10), S47-S50. -LINK

The WIN/Gallup End of Year Survey 2013 found the US was perceived to be the greatest threat to world peace by a huge margin, with 24% of respondents fearful of the US followed by: 8% for Pakistan, and 6% for China. This was followed by 5% each for: Afghanistan, Iran, Israel, North Korea. -LINK


"That's disgusting. There were clean athletes out there that have had their whole careers ruined by people like Lance Armstrong who just bended thoughts to fit their circumstances. He didn't look up cheating because he wanted to stop, he wanted to justify what he was doing and to keep that continuing on." - Nicole Cooke
Reply
#2
RE: The 100 Prisoner's problem
Maybe you should let other people tell you when things are interesting...

Boru
‘But it does me no injury for my neighbour to say there are twenty gods or no gods. It neither picks my pocket nor breaks my leg.’ - Thomas Jefferson
Reply
#3
RE: The 100 Prisoner's problem
(February 21, 2016 at 12:07 pm)BrianSoddingBoru4 Wrote: 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.
Reply
#4
RE: The 100 Prisoner's problem
(February 21, 2016 at 12:07 pm)BrianSoddingBoru4 Wrote: Maybe you should let other people tell you when things are interesting...

Boru

You owe me a keyboard.
Reply
#5
RE: The 100 Prisoner's problem
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.
Reply
#6
RE: The 100 Prisoner's problem
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!
I must not be nasty. I must not be nasty. I must not be nasty. I must not be nasty. I must not be nasty. I must not be nasty. I must not be nasty. I must not be nasty.
Reply
#7
RE: The 100 Prisoner's problem
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.
Reply
#8
RE: The 100 Prisoner's problem
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
‘But it does me no injury for my neighbour to say there are twenty gods or no gods. It neither picks my pocket nor breaks my leg.’ - Thomas Jefferson
Reply
#9
RE: The 100 Prisoner's problem
(February 21, 2016 at 2:38 pm)Tiberius Wrote: 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.
The whole tone of Church teaching in regard to woman is, to the last degree, contemptuous and degrading. - Elizabeth Cady Stanton
Reply
#10
RE: The 100 Prisoner's problem
(February 22, 2016 at 12:15 am)Cecelia Wrote:
(February 21, 2016 at 2:38 pm)Tiberius Wrote: 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.
Quote:To know yet to think that one does not know is best; Not to know yet to think that one knows will lead to difficulty.
- Lau Tzu

Join me on atheistforums Slack Cool Shades (pester tibs via pm if you need invite) Tongue

Reply



Possibly Related Threads...
Thread Author Replies Views Last Post
  Poll: You're in the Prisoner's Dilemma. shadow 35 3927 November 25, 2017 at 5:13 pm
Last Post: vorlon13
  New Take on the Prisoner's Dilemma Categories+Sheaves 0 2132 August 16, 2012 at 7:28 pm
Last Post: Categories+Sheaves



Users browsing this thread: 1 Guest(s)