This notebook is a response to this popular Veritasium video. It's a great video that's certainly worth a watch, but we felt that an interactive notebook let's you explore the problem in a way that a video never could. So here goes:

The 100 Prisoners Riddle

Prisoners are numbered 1 to $N$. In a room, $N$ boxes each contain a slip with a random prisoner's number. Each prisoner can open at most $K$ boxes to find their own number. If all prisoners succeed, they go free. Otherwise they do not.

So what strategy could you apply here?

The clever strategy: Prisoner $i$ starts at box $i$, then follows the chain (if box $i$ contains $j$, open box $j$ next). This works because permutations form cycles — a prisoner fails only if they're in a cycle longer than $K$.

To highlight this, feel free to toy around with the graph simulation below to convince yourself of this. Each node represents a box. Arrows show where each box points. Cycles are colored — red cycles are longer than $K$ (representing failure!).

You can also change the number of prisoners and the number of boxes to open if you want to play around and get a feel of the influence of these numbers.

---

Simulation: Longest Cycle Distribution

The longest cycle is important in this story, and we can simulate the distribution of that.

Extra detail

At this point you might think, "well, that's all very nice", but what if I am prisoner 42. I would select box 42 and walk along the cycle. What guarantees mee that my number is on the cycle that I am on right now?

For any position to be part of a cycle, something must point to it — that's what makes it a cycle rather than a dead end.

$... \Rightarrow a \Rightarrow 42 \Rightarrow b \Rightarrow ...$

The box that points to position 42 is, by definition, the box containing slip 42. Otherwise we would not be in a cycle!

Therefore, when prisoner 42 traverses their cycle, they must pass through this predecessor box to complete the loop, and that's exactly where their slip is.