A Hundred Prisoners and a Hundred Boxes
The puzzle
A hundred prisoners' names are placed in a hundred numbered boxes, one per box, in an unknown random order. Each prisoner in turn may open at most 50 boxes and must find their own name. They all go free only if every single one succeeds. They may agree a strategy beforehand but cannot communicate or rearrange anything once it starts.
Guessing at random gives each prisoner a 1/2 chance and the group a chance of 1 in 2^100. Find a strategy that gives better than 30%.
Stuck?
One at a time, smallest first. Open only as many as you need — the whole point of the puzzle is the part you work out yourself.
Hint 1
The prisoners cannot change their individual chances - each is still 1/2. They can change how those chances line up.
Hint 2
Each prisoner should open their own number first, then the box numbered after the name they found, and keep following that trail.
Show the answer Hide the answer
Each prisoner starts at the box with their own number and follows the chain: open box n, read the name, open that person's box, and so on. They all succeed whenever the arrangement has no cycle longer than 50 - probability 1 - ln 2, about 31%.
How to get there
The arrangement is a permutation, and every permutation splits into cycles. Starting at your own number and following the names traces exactly the cycle containing you, and your own name sits at the end of that cycle, closing it. So you find your name within 50 openings precisely when your cycle has length 50 or less.
That means all 100 succeed together if and only if the permutation has no cycle longer than 50 - a single condition, shared by everybody, instead of a hundred independent coin flips.
A random permutation of 100 has a cycle of length k > 50 with probability exactly 1/k, and at most one such cycle can exist. So the chance of failure is 1/51 + 1/52 + ... + 1/100 = 0.6882, making the chance of success 0.3118 - just over 31%. As the number of prisoners grows that harmonic tail tends to ln 2 = 0.6931, so the success probability settles at 1 - ln 2 = 0.3069 and never falls away.
The technique worth keeping
When individual probabilities cannot be improved, make them dependent. Tying every outcome to one structural property turns a hundred separate gambles into a single one, and a single gamble can be won.