100 Prisoners

[jason1990]

I think this is a very nice puzzle which got buried under a pile of crap. So here it is with its own thread.

A prison contains 100 prisoners. In a special room are 100 boxes. Each box contains the name of one of the prisoners. Tomorrow, each prisoner will be compelled to enter the room and select 50 boxes, hoping to find the box with his or her name in it. They need not select all 50 at once. They can select one, open it, then select the next, open it, and so on. If every prisoner succeeds, they are all set free. If even one prisoner fails to find his name, they are all executed. The prisoners may not communicate tomorrow, but they may communicate today. That is, they may discuss and decide upon a selection strategy. Find a strategy which guarantees they will have at least a 30% chance of being freed.

I can tell you that this puzzle is related to the stick breaking puzzle. The strategy I am thinking of will give them a probability of being executed which is very close to ln(2). It will work even if I add more boxes to the puzzle. As the number of boxes goes to infinity, their probability of being executed converges to ln(2).

[PairTheBoard]

I assume the boxes are labeled by number or kept in a fixed order? In other words, the prisoners won't go into the room and find 100 unlabled boxes scattered willy nilly all over the place.

PairTheBoard

[PairTheBoard]

I'm thinking that in the strategy they develop, they assume that all previous prisoners have been successful in their search. There should be some way that should help. They should search in a way that tends to avoid searching boxes that have already been searched and eliminated.

PairTheBoard

[jason1990]

Yes, you can assume that they are arranged in a neat row from left to right.

[jason1990]

To be clear, each prisoner will be compelled to play the game, so the game will continue even after a failure. In other words, the n-th prisoner will not know whether or not the previous prisoners succeeded.

[jay_shark]

Here is what I think so far . I thought of a well balanced strategy so that each box gets selected by exactly 50 people . Keep in mind , I'm assuming that each prisoner enters the room one at a time . Please clarify this if that's not the case .

Player 1 chooses box 1 through 50
player 2 chooses box 2 through 51
player 3 chooses box 3 through 52
.
.
player 99 chooses box 99,100,1...48
player 100 chooses box 100,1,2...49

[PairTheBoard]

[ QUOTE ]
To be clear, each prisoner will be compelled to play the game, so the game will continue even after a failure. In other words, the n-th prisoner will not know whether or not the previous prisoners succeeded.

[/ QUOTE ]

ok. So I think that makes my point more pertinent. They might as well proceed as if all previous prisoners succeeded because if one has failed it doesn't matter what they do anyway because they will all be killed.

PairTheBoard

[PairTheBoard]

ok I'm stumped. Suppose Prisoner 1 (P1) chooses boxes 1-50. Now going by the principle of avoiding boxes where you know you are not because someone else already is, the best P2 can hope to do is choose boxes 51-100. Assuming P1 has succeeded, P2 now has 50/99 to succeed. But now, the probability that both P1 and P2 succeed is,

(50/100)(50/99) = 25.25%

That means the probability that at least one will fail is 74.7%. That's already way over ln(2) and we're just getting started. I don't see how the first two prisoners can do any better than that.

PairTheBoard

[PairTheBoard]

Are the prisoners allowed to rearrange the boxes according to the names they see inside?

PairTheBoard

[jason1990]

[ QUOTE ]
Are the prisoners allowed to rearrange the boxes according to the names they see inside?

[/ QUOTE ]
I suppose the very fact that you are asking this question means I owe Aaron an apology. Okay, Aaron, sorry. Perhaps this question is not as silly as I thought.

No. You may assume the boxes are firmly secured to a surface and cannot be moved. They are made of wood and the names are carved into the inside of the boxes.