Logical Puzzles
Expert
6 min
You have 100 prisoners and 100 boxes. Each box contains one prisoner number, randomly arranged. Each prisoner may open at most 50 boxes and must find their own number. They cannot communicate after the process begins. What strategy gives a substantially better chance than random independent searching?
Hint
Think of following cycles in the permutation.
Answer
Each prisoner first opens the box bearing their own number, then follows the number found inside to the next box, continuing for at most 50 boxes.
Explanation
The arrangement of numbers forms cycles. A prisoner succeeds if the cycle containing their number has length at most 50. The strategy exploits the permutation structure instead of having every prisoner search randomly.
Step-by-Step Solution
Prisoner n opens box n.
If the box contains number m, open box m next.
Continue following the chain for up to 50 boxes.
The prisoner succeeds if their cycle length is at most 50.
If the box contains number m, open box m next.
Continue following the chain for up to 50 boxes.
The prisoner succeeds if their cycle length is at most 50.