## Prisoners and boxes

Posted on: March 22nd, 2013 by
3

This is the classic prisoners and boxes puzzle: There are 100 prisoners numbered 1,2,... 100 and 100 boxes. Each box is numbered and the number is stored inside the box as a label. The boxes are identical, there's no way to tell them apart without inspecting the labels inside. The boxes are placed in a row. The jailer announces that each prisoner will be given 50 chances to find the box that corresponds to his number. He declares that the prisoners can escape only if ALL 100 prisoners find their boxes. The prisoners are allowed some time to come up with a strategy, but after the initial session they cannot communicate. They are not allowed to change the position of the boxes either. How will the prisoners achieve a reasonable probability of success? (Note: If the prisoners choose independently, each prisoner gets his box with 50% chance, resulting in a 1 in $2^{100}$ overall chance of success. That's not reasonable. A reasonable chance is more like 20%).