The 100 prisoners problem is a probability thought exercise with an unintuitive solution, kind of like the Monty-Hall problem. The setup is this: there are 100 numbers in drawers, each corresponding to one of 100 prisoners. Each prisoner is allowed to pick 50 drawers, but the drawers are reset after each prisoner makes their choice (and there’s no communication between prisoners). The goal is for each prisoner to find their number – if that happens, they escape their sentence.
The naive solution is to pick the 50 drawers at random, giving each prisoner a 50% chance of success (and a vanishingly small chance – .50^100 – for all 100 prisoners to pick the correct number). But there’s a strategy that drastically improves the odds of success, bringing it to ~30%.
This strategy does not appear much different from the naive one, but it relies on the hidden correlation between success and failure in the permutation cycles to shape the search space. Namely, the prisoners want to search a set that’s as different as possible from everyone else’s – since they know the world where they succeed is one in which they all pick different boxes.
The the Monty Hall-inspired analogy on the Wikipedia page gives a good explanation of this. Essentially, the contestants choose doors (over two rounds) in a way that they’re never picking the same door in the same round.
Consider how the prisoners could design their choices similarly. If, in the case where each prisoner is only allowed to search a single box, all prisoners just choose box 1, there is no possibility of success: Only one prisoner will find the correct number. Choosing a box at random has some probability of success, if extremely low: 100^-100. If instead each prisoner i chooses the ith box, the chances are improved: it’s now 1/(100!), since each correctly chosen box constrains the options for future boxes. If just you expand that search to the next 50 boxes, you still don’t get the optimal solution - starting with a 1⁄2 chance of success for the first prisoner, the next 50 prisoners slowly widdle that down to 1 (the resulting probability is 50^50/(100!/50!)).
It follows along these lines that permutation cycles, being disjoint, are better for structuring the search. But I’m not sure how to make this intuition concrete, if that’s even possible.