Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Puzzle HN: 100 prisoners, 100 boxes...

news.ycombinator.com

Post reply on HN
Print view View original

1–10 of 59 posts

Puzzle HN: 100 prisoners, 100 boxes...

#1

Post by jlees »

There are 100 prisoners and a sadistic prison warden. The warden has 100 boxes labeled 1-100, in which he randomly distributes 100 pieces of paper. Each prisoner's name is written on one and only one piece of paper.

The warden says to the prisoners: "You may each open any 50 of these boxes that you choose. If all 100 of you find the box with your name in it, you may all go free. If any of you fail, you will be imprisoned forever." He tells the prisoners that they may agree on their strategy beforehand, but that he will choose them to enter the room in a random order, and they will not know anything about the previous prisoners' experiences ahead of time. They cannot move the paper around between boxes.

What are the best odds the prisoners can give themselves? (Hint: it's better than 1/2^100.)

Bonus question: in the limit as the number of prisoners goes to infinity (and correspondingly, the number of boxes), what value do the optimal odds approach?

Re: Puzzle HN: 100 prisoners, 100 boxes...

#3

Post by Someone »

I think you messed up the formulation of the problem. As stated, a strategy would be - first prisoner opens 50 boxes. - second prisoner opens the other 50. - each prisoner finds the box with the paper with his   name on it.

Success rate: 100%. There probably are other constraints but I can only guess at them (do they visit the room one by one, and must they decide on a box to choose before leaving? Who can talk to whom? Must they close all boxes before leaving the room?)

Re: Puzzle HN: 100 prisoners, 100 boxes...

#6

Post by jonafato »

Someone wrote: post #3

I think you messed up the formulation of the problem. As stated, a strategy would be - first prisoner opens 50 boxes. - second prisoner opens the other 50. - each prisoner finds the box with the paper with his name on it. Success rate: 100%. There probably are other constraints but I can only guess at them (do they visit the room one by one, and must they decide on a box to choose before leaving? Who can talk to whom…

I think the problem statement means that each prisoner must find his name independently of one another. e.g. Prisoner 1 opens 50 boxes, finds his name, then the boxes are closed and Prisoner 2 must do the same without any help.

Re: Puzzle HN: 100 prisoners, 100 boxes...

#8

Post by RiderOfGiraffes »

Some clarification:

Each prisoner finds the room in the same state as each other. After opening the boxes they are subsequently closed again before the next prisoner. I believe this was intended to be inferred from:

     ... they will not know anything about the
     previous prisoners' experiences ahead of time.
Hint - the probability of success is greater than 10%.

There is a modification of the "obvious" solution that even works if the warden knows the prisoners' strategy beforehand and behaves in a maximally pessimal (from the prisoners' point of view) manner.

Re: Puzzle HN: 100 prisoners, 100 boxes...

#9

Post by RiderOfGiraffes »

Someone wrote: post #3

I think you messed up the formulation of the problem. As stated, a strategy would be - first prisoner opens 50 boxes. - second prisoner opens the other 50. - each prisoner finds the box with the paper with his name on it. Success rate: 100%. There probably are other constraints but I can only guess at them (do they visit the room one by one, and must they decide on a box to choose before leaving? Who can talk to whom…

I believe the statement as made is correct, although not necessarily as clear as it could be.

For example, your suggested "strategy" is wrong - the first prisoner as you've stated only has a 50% chance.

Further, after each prisoner the boxes are closed so that each prisoner finds the room is exactly the same state, with no communication between them.

Re: Puzzle HN: 100 prisoners, 100 boxes...

#10

Post by o_nate »

RiderOfGiraffes wrote: post #8

Some clarification: Each prisoner finds the room in the same state as each other. After opening the boxes they are subsequently closed again before the next prisoner. I believe this was intended to be inferred from: ... they will not know anything about the previous prisoners' experiences ahead of time. Hint - the probability of success is greater than 10%. There is a modification of the "obvious" solution that even…

I can see that the prisoners can do better than 1/2^100, but I don't see how they could get anywhere close to 10% success - so I must be missing something big here.
Post reply on HN