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 overall chance of success. That's not reasonable. A reasonable chance is more like 20%).

Can you exchange the labels if not the boxes?

No, you are not allowed to exchange the labels. You are not allowed to change the location of the boxes either.

Does the prisoner choose 50 boxes and open them all at once? Or can he do it adaptively based on what he finds in the box one-at-a-time? I was trying the former case where you could use conditional probabilities to group favorable events together, but the calculations were cumbersome even for smaller values though it seems like you could do much better than 1/2^n.