# Prisoners and Boxes

XanthosNZ
Posers and Puzzles 07 Dec '06 07:47
1. XanthosNZ
Cancerous Bus Crash
07 Dec '06 07:47
100 prisoners are given the sort of crazy deal they always get in these problems. Each prisoner gets a number. There's a room with 100 identical boxes in a row, each containing a random number from 1-100, with no repeats. Each prisoner, in turn and isolated from all the others, will get a chance to open 50 boxes of his choosing, one at a time. If each prisoner manages to find his own number in one of the 50 boxes he opens, all prisoners go free. The prisoners can make a strategy together at the beginning, but there can be no communication afterwards. The room is completely unmarkable, and will be reset to the exact same starting state for each prisoner.
Clearly if every prisoner picked randomly the probability that that prisoner would be successful would be 0.5 and therefore the probability they would all be successful would be 0.5^100 (read:practically zero, actually it's ~8*10^-31). What is the optimal strategy that the prisoners should use?
2. AThousandYoung
All My Soldiers...
07 Dec '06 10:553 edits
The prisoners don't get to watch other prisoners pick, right? Can they communicate via bonks on the wall or something?

If the outside prisoners cannot get information from prisoners inside, then it's hard to see what they can do.
3. 07 Dec '06 11:25
A very interesting problem indeed.
I have no idea about the solution so I eagerly wait for the correct answer and the explanation.
4. 07 Dec '06 11:53
I think I see a way to make sure the probability they all succeed is 0.5. I won't post it yet - see what else comes up.
5. 07 Dec '06 12:33
I'm just throwing out this completely random response. Each prisoner takes their Sharpie Marker in with them and marks each number in the boxes they picked on the bottom of the box. the first prisoner marks half the boxes then if the second prisoner doesnt see his/her number he opens the other half of the boxes. ðŸ˜€ I know this isn't the right answer.
6. 07 Dec '06 14:45
I've seen this one before. I couldn't work it out and found the answer quite surprising - if I remember correctly they have roughly a 1 in 3 chance of surviving.
7. 07 Dec '06 15:53
Originally posted by mtthw
I think I see a way to make sure the probability they all succeed is 0.5. I won't post it yet - see what else comes up.
OK, I've re-read the question, and that was wrong. Glad I didn't post it now ðŸ™‚
8. PBE6
Bananarama
07 Dec '06 16:00
Can the prisoners communicate in a roundabout way by picking the boxes in order, then waiting a specified length depending on the numbers they pick? I haven't checked yet, but there must be some function that makes the amount of time spent a unique sum given a unique set of numbers. Eventually, the whole set of boxes should be mapped out guaranteeing success for the remaining prisoners.
9. 07 Dec '06 18:00
All prisoners choose the same 50 boxes, say the left 50. You didn't say the prisoners received a unique number between 1-100. They might all have the same number.
10. PBE6
Bananarama
07 Dec '06 18:34
Just did a quick Google, and found a detailed solution that I couldn't help but read. ðŸ˜ž But a very interesting problem, with a very interesting and counter-intuitive answer.
11. 07 Dec '06 19:441 edit
A brilliant puzzle.
ðŸ™‚
OK I admit it, I have no clue!
12. 07 Dec '06 20:21