100 Prisoners Puzzle
Thread Rating:
July 11th, 2022 at 5:13:53 PM
permalink
It's time for another evil warden puzzle.
In this case, the warden gets together 100 prisoners and gives each a unique number from 1 to 100.
Inside another room are 100 numbered boxes. The warden takes pieces of paper, numbered 1 to 100, and randomly places them in the boxes, one piece per box.
The next day, the prisoners will be allowed into the boxes room one at a time. Each prisoner may open 50 boxes. If a prisoner finds his own number (for example prisoner 23 finds the box containing the numbers 23) then he will be "successful" and may leave early if he finds it before the 50th opening.
If all 100 prisoners are successful, they will all be set free. However, if one or more are unsuccessful, then they are all immediately put to death.
The prisoners are allowed a day together to strategize. Once the first prisoner enters the boxes room, no further communication is allowed.
What strategy will maximize their probability of being set free?
For extra credit, what is a mathematical expression of this probability as the number of prisoners approaches infinity, where each may open half the boxes?
Please do not just throw out a YouTube video explaining the answer. The purpose of these puzzles is not the answer itself, but the challenge of finding the answer yourself.
In this case, the warden gets together 100 prisoners and gives each a unique number from 1 to 100.
Inside another room are 100 numbered boxes. The warden takes pieces of paper, numbered 1 to 100, and randomly places them in the boxes, one piece per box.
The next day, the prisoners will be allowed into the boxes room one at a time. Each prisoner may open 50 boxes. If a prisoner finds his own number (for example prisoner 23 finds the box containing the numbers 23) then he will be "successful" and may leave early if he finds it before the 50th opening.
If all 100 prisoners are successful, they will all be set free. However, if one or more are unsuccessful, then they are all immediately put to death.
The prisoners are allowed a day together to strategize. Once the first prisoner enters the boxes room, no further communication is allowed.
What strategy will maximize their probability of being set free?
For extra credit, what is a mathematical expression of this probability as the number of prisoners approaches infinity, where each may open half the boxes?
Please do not just throw out a YouTube video explaining the answer. The purpose of these puzzles is not the answer itself, but the challenge of finding the answer yourself.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
July 11th, 2022 at 5:27:07 PM
permalink
I will refrain from answering as I saw that youtube video yesterday.
At my age, a "Life In Prison" sentence is not much of a deterrent.
July 11th, 2022 at 6:15:19 PM
permalink
A couple clarifying questions.. putting in tags just in case this happens to be key towards the solution and people don't want that spoiled:
Are the prisoners allowed to manipulate the contents of the boxes?
- Can they move paper between boxes?
- Can they stuff multiple papers into a single box (thus opening one box would reveal multiple numbers)?
- Can they leave boxes open, or does each prisoner start with a room full of closed boxes?
- Can you peek into a box that is already open, or does that still count as 1/ attempts?
- If a prisoner succeeds, does that reduce the number of potential boxes to open for the next one, or is each prisoner, regardless of their #, face with the same 100 boxes in exactly the same state as the prisoners before them?
I feel there has to be something like the above that allows optimizing/communication.
Or, given the forum, is this purely about mathematical optimization, as in "since we know prisoners before me opened THEIR number, I must reduce the likelihood of me opening THE SAME box, as by definition, their number is not my number."
Are the prisoners allowed to manipulate the contents of the boxes?
- Can they move paper between boxes?
- Can they stuff multiple papers into a single box (thus opening one box would reveal multiple numbers)?
- Can they leave boxes open, or does each prisoner start with a room full of closed boxes?
- Can you peek into a box that is already open, or does that still count as 1/ attempts?
- If a prisoner succeeds, does that reduce the number of potential boxes to open for the next one, or is each prisoner, regardless of their #, face with the same 100 boxes in exactly the same state as the prisoners before them?
I feel there has to be something like the above that allows optimizing/communication.
Or, given the forum, is this purely about mathematical optimization, as in "since we know prisoners before me opened THEIR number, I must reduce the likelihood of me opening THE SAME box, as by definition, their number is not my number."
July 11th, 2022 at 6:27:58 PM
permalink
Quote: MukkeA couple clarifying questions.. putting in tags just in case this happens to be key towards the solution and people don't want that spoiled:
link to original post
The prisoner's must leave the boxes and papers exactly as they were when they entered the room. No switching papers. No leaving lids open. If the warden detects any such attempts to convey information, he will immediately kill all 100 prisoners.
Prisoners must exist the boxes room by a different door than they entered, so nobody will know the outcome of the other prisoners until all 100 have had their turn.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
July 11th, 2022 at 7:08:53 PM
permalink
It seems to me that the answer must have something to do with gambling i.e. that although no matter what each prisoner does he will still at the end of the exercise have a 50-50 chance of survival, but via some kind of methodology there will be some kind of distribution of results that may give some of them a greater chance of surviving which would be imparted to them as a whole giving the collective group a possibly greater chance at survival.
In other words, don't flat bet, take a chance, vary your bets.
In other words, don't flat bet, take a chance, vary your bets.
Last edited by: MDawg on Jul 11, 2022
I tell you it’s wonderful to be here, man. I don’t give a damn who wins or loses. It’s just wonderful to be here with you people.
https://wizardofvegas.com/forum/gambling/betting-systems/33908-the-adventures-of-mdawg/
July 12th, 2022 at 6:22:14 AM
permalink
Quote: MDawgIt seems to me that the answer must have something to do with gambling i.e. that although no matter what each prisoner does he will still at the end of the exercise have a 50-50 chance of survival, but via some kind of methodology there will be some kind of distribution of results that may give some of them a greater chance of surviving which would be imparted to them as a whole giving the collective group a possibly greater chance at survival.
link to original post
It's easy to say the best strategy maximizes the chance of success for the entire group. It doesn't make any difference whether 1 person or all 100 are wrong.
Under the optimal strategy, the group will either be successful or there will be at least 51 prisoners who don't find their box.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
July 12th, 2022 at 6:25:08 AM
permalink
This sounds the same as the
Secret Santa puzzle that there’s a thread on here about somewhere. I remember being surprised by the answer. How it finally made sense to me was the answer makes all the guesses pick in a highly correlated fashion.
The race is not always to the swift, nor the battle to the strong; but that is the way to bet.
July 12th, 2022 at 9:08:41 AM
permalink
Each prisoner picks the box that is labeled with his own number. 99% of the time his own number will not be in that box and he will see a different number -in which case he then goes to the box of the number that was in his previous box and opens it and looks at that number. He keeps repeating that action until he finds his number or reaches 50 boxes without any success.
Explanation: You have 100 boxes with the numbers 1-100 randomly placed within them. Whatever the random arrangement, you can think of the 100 boxes as being partitioned into a group of chains of varying lengths.
If box 50 contains the number 50, then that is a chain of length 1.
If box 8 contains the number 23 and box 23 has the number 8 then that is a chain of length 2.
If box 17 contains the number 99, box 99 contains the number 82 and box 82 contains the number 17 then that is a chain of length 3.
Whatever the arrangement, each box is only in one unique chain, and each number in a box is only in one unique chain. By starting with the box that is the number you are looking for, you ensure that you are in the chain that will eventually lead to your number! You don't know whether it will be a chain that is longer or shorter than 50 boxes -but you know you will get there eventually.
I haven't yet worked out how to do the math, but all the prisoners will survive whenever the 100 boxes do not contain a chain that is longer than 50. I think it is related to the partitions of the number 100; i.e., the number of partitions of the number 100 that do not have a part that is greater than 50.
Ex: If the 100 boxes are divided into eight chains of these lengths: 28-22-10-10-10-7-2-1, then the prisoners will survive.
If the partition of 100 is 58-40-1-1, the prisoners will die, because one of the chains has a length longer than 50.
Last edited by: gordonm888 on Jul 12, 2022
So many better men, a few of them friends, are dead. And a thousand thousand slimy things live on, and so do I.
July 12th, 2022 at 10:04:03 AM
permalink
Quote: gordonm888
Each prisoner picks the box that is labeled with his own number. 99% of the time his own number will not be in that box and he will see a different number -in which case he then goes to the box of the number that was in his previous box and opens it and looks at that number. He keeps repeating that action until he finds his number or reaches 50 boxes without any success.
Explanation: You have 100 boxes with the numbers 1-100 randomly placed within them. Whatever the random arrangement, you can think of the 100 boxes as being partitioned into a group of chains of varying lengths.
If box 50 contains the number 50, then that is a chain of length 1.
If box 8 contains the number 23 and box 23 has the number 8 then that is a chain of length 2.
If box 17 contains the number 99, box 99 contains the number 82 and box 82 contains the number 17 then that is a chain of length 3.
Whatever the arrangement, each box is only in one unique chain, and each number in a box is only in one unique chain. By starting with the box that is the number you are looking for, you ensure that you are in the chain that will eventually lead to your number! You don't know whether it will be a chain that is longer or shorter than 50 boxes -but you know you will get there eventually.
I haven't yet worked out how to do the math, but all the prisoners will survive whenever the 100 boxes do not contain a chain that is longer than 50. I think it is related to the partitions of the number 100; i.e., the number of partitions of the number 100 that do not have a part that is greater than 50.
Ex: If the 100 boxes are divided into eight chains of these lengths: 28-22-10-10-10-7-2-1, then the prisoners will survive.
If the partition of 100 is 58-40-1-1, the prisoners will die, because one of the chains has a length longer than 50.
link to original post
You present the correct strategy. Your next task is to calculate the probability of success following your strategy?
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
July 12th, 2022 at 10:06:32 AM
permalink
Quote: unJonThis sounds the same as the
Secret Santa puzzle that there’s a thread on here about somewhere. I remember being surprised by the answer. How it finally made sense to me was the answer makes all the guesses pick in a highly correlated fashion.
link to original post
See Previous Thread - Secret Santa Problem #2.
July 12th, 2022 at 10:08:27 AM
permalink
Quote: unJonThis sounds the same as the
Secret Santa puzzle that there’s a thread on here about somewhere. I remember being surprised by the answer. How it finally made sense to me was the answer makes all the guesses pick in a highly correlated fashion.
link to original post
Yes, I forgot we discussed that. Here is a link to the Secret Santa puzzle.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
July 12th, 2022 at 11:23:50 AM
permalink
I'm thrashing around on the probability formula. Here is a probability table relevant to 5 prisoners looking for their number in 5 boxes
Note that the total permutations of 5 are 5! =120, i.e., there are 120 possible ways for the 5 numbers to be arranged in 5 boxes .
So, given this table (and assuming its correct), if the prisoners are allowed to look in 3 boxes they have a 55% chance of surviving. If they are allowed to look in only two boxes, they have only a 21.6667% chance of surviving.
Among many fascinating things about this problem, I find it very interesting that this assigns a fundamental probability of occurrence to the partitions of any number n.
Note that the total permutations of 5 are 5! =120, i.e., there are 120 possible ways for the 5 numbers to be arranged in 5 boxes .
| Partition | Permuted Combinations | Probability of Partition |
|---|---|---|
| 5 | 24 | 0.2 |
| 4-1 | 30 | 0.25 |
| 3-2 | 20 | 0.166666667 |
| 3-1-1 | 20 | 0.166666667 |
| 2-2-1 | 15 | 0.125 |
| 2-1-1-1 | 10 | 0.083333333 |
| 1-1-1-1-1 | 1 | 0.008333333 |
So, given this table (and assuming its correct), if the prisoners are allowed to look in 3 boxes they have a 55% chance of surviving. If they are allowed to look in only two boxes, they have only a 21.6667% chance of surviving.
Among many fascinating things about this problem, I find it very interesting that this assigns a fundamental probability of occurrence to the partitions of any number n.
So many better men, a few of them friends, are dead. And a thousand thousand slimy things live on, and so do I.
