The names of 100 prisoners are placed in 100 wooden boxes, one name to a box, and the boxes are lined up on a table in a room. One by one, the prisoners are led into the room; each may look in at most 50 boxes, but must leave the room exactly as he found it and is permitted no further communication with the others.
The prisoners have a chance to plot their strategy in advance, and they are going to need it, because unless every single prisoner finds his own name all will subsequently be executed.
Find a strategy for them which has probability of success exceeding 30%.

Comment: If each prisoner examines a random set of 50 boxes, their probability of survival is an unenviable 1/2¹⁰⁰ ∼ 0.0000000000000000000000000000008. They could do worse—if they all look in the same 50 boxes, their chances drop to zero. 30% seems ridiculously out of reach—but yes, you heard the problem correctly!

(In reply to re: This is not possible. by broll)

Looking at the case with 6 prisoners, 6 boxes and a choice of 3 boxes, prisoner 1 again has a 50% chance of getting the right box (360/720). Specifically, prisoner 1 has 120/720 chances to find his own box straight away - 120+5*48 = 360, his overall 50% chance.

Without doing a massive post, let's just consider the case where a 4 appeared in the first box. Of the (48/120) cases where prisoner 1 succeeded, prisoner 2 has a remarkably high rate of success (87.5%):

2 opens his own box to find a 2:
1  {4, 2, 1, 3, 5, 6}, 
2  {4, 2, 1, 3, 6, 5} 
3 {4, 2, 3, 1, 5, 6}, 
4 {4, 2, 3, 1, 6, 5},  
5  {4, 2, 3, 5, 1, 6} 
6 {4, 2, 3, 6, 5, 1}, 
7 {4, 2, 5, 1, 3, 6},  
8 {4, 2, 5, 1, 6, 3} 
9  {4, 2, 5, 6, 3, 1}, 
10 {4, 2, 6, 1, 3, 5}, 
11 {4, 2, 6, 1, 5, 3}, 
12 {4, 2, 6, 5, 1, 3}, 

2 opens his own box to find a number that leads at one remove to his own number:
1 {4, 3, 2, 1, 5, 6},  
2 {4, 3, 2, 1, 6, 5}, 
3 {4, 3, 2, 5, 1, 6}, 
4 {4, 3, 2, 6, 5, 1}, 
5 {4, 5, 1, 3, 2, 6},  
6 {4, 5, 3, 1, 2, 6}, 
7 {4, 5, 3, 6, 2, 1} 
8 {4, 5, 6, 1, 2, 3} 
9 {4, 6, 1, 3, 5, 2} 
10 {4, 6, 3, 1, 5, 2}, 
11 {4, 6, 3, 5, 1, 2} 
12 {4, 6, 5, 1, 3, 2} 

2 opens his own box to find a number that leads to 2 indirectly:
1 {4, 1, 3, 2, 5, 6} 
2 {4, 1, 3, 2, 6, 5} 
3 {4, 1, 5, 2, 3, 6}, 
4 {4, 1, 5, 2, 6, 3}, 
5 {4, 1, 6, 2, 3, 5}, 
6 {4, 1, 6, 2, 5, 3}, 
7 {4, 3, 5, 1, 2, 6}, 
8  {4, 3, 5, 6, 2, 1} 
9 {4, 3, 6, 1, 5, 2}, 
10 {4, 3, 6, 5, 1, 2} 
11 {4, 5, 1, 3, 6, 2} 
12 {4, 5, 2, 1, 3, 6}, 
13 {4, 5, 2, 6, 3, 1},  
14 {4, 5, 3, 1, 6, 2}, 
15 {4, 6, 1, 3, 2, 5} 
16 {4, 6, 2, 5, 1, 3} 
17 {4, 6, 2, 1, 5, 3} 
18 {4, 6, 3, 1, 2, 5} 

2 fails to find his number
1 {4, 3, 5, 1, 6, 2} 
2 {4, 3, 6, 1, 2, 5} 
3 {4, 5, 2, 1, 6, 3} 
4 {4, 5, 6, 1, 3, 2} 
5 {4, 6, 2, 1, 3, 5} 
6 {4, 6, 5, 1, 2, 3} 

Of the cases where prisoner 1 found his own box straight away, prisoner 2 has an enhanced prospect of success; he will either find his own number straight away (24/120) or at one remove (also 24/120) or indirectly (also 24/120), for an overall probability of 72/120.

Collectively this translates to a probability of almost 40%, much better might be expected with a random selection of boxes.

Posted by broll on 2017-04-12 16:09:14