All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Names in Boxes (Posted on 2017-04-09)
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/2100 ∼ 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!

Comments: ( Back to comment list | You must be logged in to post comments.)
 re(2): This is not possible - further thoughts. Comment 10 of 10 |
(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

 Search: Search body:
Forums (0)