One of the most striking results in interview mathematics, because the improvement is so extreme.
The setup
100 prisoners, numbered. A room holds 100 boxes, each containing one prisoner's number in random order. Each prisoner enters alone, may open 50 boxes, and must find their own number. They all survive only if every prisoner succeeds. No communication once it starts; they may agree a strategy beforehand.
The naive answer
Each prisoner opens 50 random boxes and succeeds with probability 1/2. All 100 succeed with probability (1/2)^100 - about 1 in 10^30. Effectively zero.
The strategy
Each prisoner opens the box labelled with their own number. Whatever number is inside, they go to the box with that label next. Repeat up to 50 times.
This gives all 100 prisoners a survival probability of about 31%.
Why it works
The box arrangement is a permutation, which decomposes into cycles. Starting at your own number and following the contents traces the cycle containing you - and that cycle necessarily returns to your number, since the permutation is a bijection.
So you find your number within 50 steps exactly when your cycle has length at most 50.
Everyone succeeds precisely when the permutation contains no cycle longer than 50.
The probability
For a random permutation of 2n elements, there can be at most one cycle longer than n. The probability that a cycle of length exactly k > n exists is 1/k. So the failure probability is
1/51 + 1/52 + ... + 1/100 ≈ ln 2 ≈ 0.693
giving survival ≈ 30.7%. As n grows this converges to 1 - ln 2, independent of the number of prisoners.
The insight to articulate
Individual chances are still 1/2 each - the strategy does not improve any single prisoner's odds. What it does is make the outcomes maximally correlated: instead of 100 independent coin flips, there is essentially one shared event. Correlating failures is what rescues a conjunction.
That principle - when you need everything to work, correlate the risks - is a genuinely useful idea beyond the puzzle.
Practise in brainteasers.