100 Prisoners & 100 Boxes

The Puzzle: 100 prisoners are numbered 1 to 100. A room contains 100 boxes, each with a unique prisoner’s number inside (shuffled randomly).

• One by one, each prisoner enters the room and can open 50 boxes.
• They must find the box containing their own number.
• They must leave the room exactly as they found it and cannot communicate with prisoners who haven’t entered yet.
• The Rule: If all 100 prisoners find their own numbers, they are set free. If even one fails, they are all executed. What is their best strategy?

1. The Random approach

If everyone picks 50 boxes randomly, the probability of success is $(1/2)^\{100\}$, which is effectively zero.

2. The Winning Strategy: Pointer Following

Each prisoner uses the numbers as “pointers”:

1. Prisoner $k$ first opens box $k$.
2. If it contains number $k$, he is done (Success!).
3. If it contains another number $j$, he next opens box $j$.
4. He repeats this until he either finds number $k$ or has opened 50 boxes.

3. Why it Works

This setup divides the boxes into Cycles. For example: Box 1 has 5, Box 5 has 2, Box 2 has 1. (Cycle: $1 \to 5 \to 2 \to 1$).

• A prisoner will find their number if and only if they are part of a cycle of length 50 or less.
• The group succeeds if there is no cycle longer than 50 in the permutation.
• The Probability: Mathematically, the chance of a random permutation having no cycle longer than 50 is about 31%.

---

Interview-Focused Questions

Key Takeaway

This is the ultimate FAANG puzzle. It tests your knowledge of Permutations and your ability to see “hidden structures” (cycles) in random data.