100 Prisoners

[jason1990]

[ QUOTE ]
ok I'm stumped.

[/ QUOTE ]
Maybe this will help.

[ QUOTE ]
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.

[/ QUOTE ]

[jason1990]

[ QUOTE ]
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 .

[/ QUOTE ]
It is the case.

[ QUOTE ]
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

[/ QUOTE ]
Under this strategy, what is the probability of freedom?

[marv]

[ QUOTE ]
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).

[/ QUOTE ]

[Note this is not a solution, just some thoughts and sim results. No previous knowledge of continued fractions is assumed.]

Consider 2 prisoners, p1 and p2. If p1 does boxes 1-50 and p2 does 51-100 then p(survive) will be close to 0.25, so thats no good. What we want is that when p1 finds p2's name during his search then p2 will tend to search the same boxes as p1, and vice-versa, but when p1 doesn't find p2's name in his search then they tend to search non-overlapping sets of boxes.

This suggests trying the following: p1 starts searching boxes 1-50 but if he finds p2's name, he immediately switches to box 51 and continues searching 52, 53 etc. . p2 starts searching boxes 51-100 but if he finds p1's name he switches to box 1 and continues searching 2,3,4 ..

There are 4 cases depending on where the boxes containing the names of p1 and p2 are:

1-50 51-100
none both die
both none die
p1 p2 survive
p2 p1 survive about half the time

In the last case, if p1 is in box 50+r and p2 is in box s then we survive provided s+r<=50, which is close to half the time.

Thus we survive about 0.375 the time, converging to 0.375 for large number of boxes.

For >2 prisoners, this suggests the following algorithm: Prisoner i starts by searching box i. Then if his last opened box revealed the name of prisoner j, search box j next.

For 100 prisoners and 100 boxes, a simulation of 9M runs gave p(survive)=0.311724 which is just a little more than 1-ln(2)=0.3068.

Marv

[PairTheBoard]

[ QUOTE ]
[ QUOTE ]
ok I'm stumped.

[/ QUOTE ]
Maybe this will help.

[ QUOTE ]
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.

[/ QUOTE ]

[/ QUOTE ]

I think it's clear that no matter what strategy P1 uses to choose his next box, he will have a 50% chance to succeed. As I showed in my last post, P2 will need some kind of strategy piggybacking on P1 that greatly improves what would normally be P2's 50% chance to succeed. Otherwise, the chance one of them fails is about 75%, already way over ln(2).

Suppose P1 does something like this. He starts out choosing the boxes B1,B2,... in order. But if he encounters P2's box along the way he switches to B100,B99,B98,.... Something like that. Can P2 piggyback on P1's strategy in a way that greatly improves P2's normal 50% chance to succeed? I don't know. Doesn't seem like it. I'll think some more.

If you can't get it to work for just P1 and P2 I don't see how any argument for the whole lot of them is going to make it any better.


PairTheBoard

[PairTheBoard]

[ QUOTE ]
[ QUOTE ]
[ QUOTE ]
ok I'm stumped.

[/ QUOTE ]
Maybe this will help.

[ QUOTE ]
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.

[/ QUOTE ]

[/ QUOTE ]

I think it's clear that no matter what strategy P1 uses to choose his next box, he will have a 50% chance to succeed. As I showed in my last post, P2 will need some kind of strategy piggybacking on P1 that greatly improves what would normally be P2's 50% chance to succeed. Otherwise, the chance one of them fails is about 75%, already way over ln(2).

Suppose P1 does something like this. He starts out choosing the boxes B1,B2,... in order. But if he encounters P2's box along the way he switches to B100,B99,B98,.... Something like that. Can P2 piggyback on P1's strategy in a way that greatly improves P2's normal 50% chance to succeed? I don't know. Doesn't seem like it. I'll think some more.

If you can't get it to work for just P1 and P2 I don't see how any argument for the whole lot of them is going to make it any better.


PairTheBoard

[/ QUOTE ]

ok so I think this has a chance of working. P1 proceeds as above. He starts with Boxes B1,B2,.... If he encounters P2's box he switches to B100,B99,.... Now P2 starts at B100,B99,B98. If he encounters P1's Box he switches to B1,B2,B3...

Conditioning on P1 being successful. If P1 is succesful without switching then we know P2's box is not among the the boxes B1,B2,...,B(P1). In this case, P2's chance of success is 50/(100-B(P1)). That should be much better than 50%.

In the case where P2 is successful with a switch. P2 will always encounter P1's box while searching B100,B99,B98.... He will then switch and always encounter his box searching B1,B2,B3,... P2 will never fail in this case because the total boxes searched by P1 will be at most 50, and P2 will be searching only boxes already searched by P1. So this case gives P2 a 100% chance of success. A beaucoup improvement over his normal 50% chance.

I'm not sure how to handle the probabilty in Case 1 though. It's tempting to say P2's chance of success in that case is something like 50/(100-E[B(P1)]). But that's not so clear to me. EV's in the denominator make me nervous.

PairTheBoard

[PairTheBoard]

oops. I didn't see Marv's post. Looks like he has solved it. Now can we prove his method works without the simulation?

PairTheBoard

[djames]

[ QUOTE ]
oops. I didn't see Marv's post. Looks like he has solved it. Now can we prove his method works without the simulation?

PairTheBoard

[/ QUOTE ]

Yes. Think combinatorics. I promised I wouldn't give the solution, since I have already seen this one years ago in school, but I'm not quite sure if aiding in a direct proof of a solution that you all found is cheating or not.

Interestingly, this solution has been proved to be the best possible algorithm the prisoners could employ!

[marv]

[ QUOTE ]
[ QUOTE ]
oops. I didn't see Marv's post. Looks like he has solved it. Now can we prove his method works without the simulation?

PairTheBoard

[/ QUOTE ]

Yes. Think combinatorics. I promised I wouldn't give the solution, since I have already seen this one years ago in school, but I'm not quite sure if aiding in a direct proof of a solution that you all found is cheating or not.

Interestingly, this solution has been proved to be the best possible algorithm the prisoners could employ!

[/ QUOTE ]

OK I think I've got it.
[SPOILER]






Let N be the number boxes/prisoners.
Let f(i) be the name of the prisoner in box i.
Prisoner j will find his name iff the sequence

f(j), f(f(j)), ... f^50(j)

contains j,

Now think of f as a directed graph G with an edge from i to f(i) for each i. Since f is a permutation every vertex in G has in-degree=out-degree=1, so G is a union of cycles, and j will find his name iff the cycle containing j has length <= 50.

Given the hint about the stick problem, I think we want to show that we can construct a graph with the same distribution as G as follows. Start with an empty graph on N nodes. Pick U uniform on [1,N] and add the cycle

1, 2, 3, 4, ..., U, 1

to G. Now repeat on the set of remaining nodes (which still have no edges). Then re-label the vertices of G by picking a random permutation of the labels {1,2,..,N}. This will give the correct distribution provided the distribution of the length of each cycle is correct, so we just need to show that the size of the orbit of j under iterating f has a length which is uniform on the number of boxes.

Now the correct distribution for the length of the first cycle is given by

p(length = 1) = p(f(1) = 1) = 1/N
p(length = 2) = p(f(1) != 1 && f(f(2)) == 1)
= (1-1/N) * 1/(N-1)
= (N-1)/N * 1/N-1
= 1/N
p(length = 3) = p(f(1) != 1 && f(f(1)) != 1 && f(f(f(1)))=1)
= (1-1/N) * (1-1/(N-1)) * 1/(N-2)
= (N-1)/N * (N-2)/(N-1) * 1/(N-2)
= 1/N

etc.

Thus the distribution of the length of the cycle is indeed uniform and the graph construction gives a function f which is uniform on the set of all permutations of 1..N.

Hence p(we all die) = p(some cycle is length >= N/2) which is exactly the stick problem (in the limit of large N).

Marv

[djames]

[ QUOTE ]
j will find his name iff the cycle containing j has length <= 50

[/ QUOTE ]

For those that don't want to wade through the stick breaking problem:

For k > n/2 (i.e. k > 50), we note there can be at most 1 k-cycle in a permutation on n letters.

There are (n k)(k-1)!(n-k)! = n!/k ways to pick a k-cycle. Since there are n! permutations, the probability there is a k-cycle is 1/k. Thus 1 - (1/51 + 1/52 + ... + 1/100) is the probability there is no k-cycle where k>50. This sum converges to 1 - ln(2) as n gets large.

[jason1990]

Nice solution, marv. I actually think djames's solution is the one more commonly presented. But it is your solution which led me to think of the stick problem and to see it as a limiting version of the prisoner problem.

Edit: Here is something interesting. You observed that the length of the cycle containing 1 is uniform on {1,...,N}. You combined this observation with the solution to the stick puzzle to solve the prisoner puzzle. But you could have combined this observation with djames's solution to the prisoner puzzle to solve the stick puzzle. So this makes the 4th (valid) solution to the stick puzzle so far.