One Hundred Prisoners, Fifty Opens

A Puzzle With a Famous Wrong Answer

A hundred prisoners are numbered one to a hundred. In a room stand a hundred boxes, and inside each box is one prisoner’s name, shuffled at random. One at a time, each prisoner enters and may open fifty boxes, looking for his own name. Then the room is restored exactly as it was and the next one enters. No messages, no marks, nothing left behind.

They all go free only if every single one of them finds his own name. Otherwise none of them does.

Almost everybody who meets this puzzle gives the same answer, and it is wrong by about thirty orders of magnitude.

The same argument in under three minutes. The written version, with the code, is below.

What Chance Alone Gives Them

Suppose each prisoner simply opens fifty boxes at random. Each has an even chance of finding his name, and with no way to communicate, the hundred attempts look independent. So the probability that all hundred succeed is one half multiplied by itself a hundred times:

$$p_{\text{random}} \;=\; \left(\tfrac{1}{2}\right)^{100} \;=\; 7.9 \times 10^{-31} \;\approx\; \frac{1}{1.27 \times 10^{30}}.$$

$(1)$

That is not a small probability, it is an absurd one. If every atom in a hundred million galaxies tried once a second for the age of the universe, you would still be waiting. The puzzle is famous because that answer feels not merely likely but forced: there is nothing to coordinate on, so what could possibly be done?

The Strategy, in One Sentence

There is a strategy that succeeds thirty-one times in a hundred.

Each prisoner opens the box carrying his own number. Inside is a name. He then opens the box carrying that name, reads the name inside, opens that box, and continues until he finds his own name or has opened fifty boxes.

That is the whole of it. Nothing is agreed on the night, nothing is signalled, nothing is left behind. Every prisoner follows the same rule, and the rule refers only to what he himself has just seen.

Why It Works

The shuffle is not a hundred independent placements. A permutation of a hundred items decomposes into closed cycles: box seven holds name forty, box forty holds name eleven, box eleven holds name seven, and the loop shuts.

A prisoner who starts at his own number is walking his own cycle. Because the cycle is closed and he entered it at his own number, the only way back to the start is through the box that contains his name. He will find it, on the last step of the loop, provided the loop has fifty boxes or fewer.

So no prisoner fails alone, and no prisoner succeeds alone. Everybody on a short cycle succeeds; everybody on a long one fails together.

Python 3.13 — cycle structure and the exact probability

import numpy as np
import matplotlib
matplotlib.use("Agg")
import matplotlib.pyplot as plt

N, HALF, TRIALS = 100, 50, 200_000
NAVY, TEAL, AMBER, INK, GREY = "#1e3a5f", "#2a9d8f", "#c0851f", "#1a1a1f", "#8a8f98"

def cycles(p):
    """Cycle lengths of the permutation p, where p[i] is the name in box i."""
    seen = np.zeros(len(p), bool)
    out = []
    for s in range(len(p)):
        if seen[s]:
            continue
        n, c = s, 0
        while not seen[n]:
            seen[n] = True
            n = p[n]
            c += 1
        out.append(c)
    return out

# a run fails exactly when SOME cycle is longer than fifty
exact = 1.0 - sum(1.0 / k for k in range(HALF + 1, N + 1))
assert abs(exact - 0.311827821) < 1e-8

rng = np.random.default_rng(4)
longest = np.array([max(cycles(rng.permutation(N))) for _ in range(TRIALS)])
assert abs((longest <= HALF).mean() - exact) < 0.005      # simulation agrees
assert cycles(np.roll(np.arange(N), 1)) == [N]            # a rotation is one cycle
assert max(cycles(np.arange(N))) == 1                     # the identity is fixed points

# ---- figure 1: two nights, one bar per cycle -------------------------------
r = np.random.default_rng(11)
good = bad = None
while good is None or bad is None:
    c = sorted(cycles(r.permutation(N)), reverse=True)
    if max(c) <= HALF and good is None:
        good = c
    elif max(c) > HALF and bad is None:
        bad = c

fig, ax = plt.subplots(1, 2, figsize=(13.0, 5.6), facecolor="white", sharex=True)
for a, c, title, ok in ((ax[0], good, "a night they all live", True),
                        (ax[1], bad, "a night nobody does", False)):
    show = c[:12]
    for i, L in enumerate(show):
        over = L > HALF
        a.barh(len(show) - i, L, height=.68, color=(AMBER if over else TEAL),
               edgecolor="white", linewidth=1.0)
        a.text(L + 1.5, len(show) - i, str(L), va="center", fontsize=12,
               color=(AMBER if over else INK), weight="bold")
    if len(c) > 12:
        a.text(2, 0.2, f"+ {len(c) - 12} shorter cycles", fontsize=12, color=GREY, va="center")
    a.axvline(HALF, color=INK, lw=2.2, ls="--")
    a.text(HALF + 1.5, len(show) + .9, "fifty opens", fontsize=12, color=INK, va="center")
    a.set_title(f"{title}   ·   longest cycle {max(c)}", fontsize=14,
                color=(AMBER if not ok else TEAL))
    a.set_yticks([]); a.set_xlim(0, N); a.set_ylim(-0.4, len(show) + 1.8)
    for sp in ("top", "right", "left"):
        a.spines[sp].set_visible(False)
    a.set_xlabel("length of each cycle", fontsize=14)
plt.tight_layout(pad=1.4)
fig.savefig("fig_1.png", dpi=150, bbox_inches="tight", facecolor="white")
plt.close(fig)

# ---- figure 2: the longest cycle over two hundred thousand nights ----------
fig, a = plt.subplots(figsize=(13.0, 6.0), facecolor="white")
bins = np.arange(1, N + 2)
h, _ = np.histogram(longest, bins=bins)
frac = h / h.sum()
a.bar(bins[:-1], frac, width=1.0,
      color=[TEAL if b <= HALF else AMBER for b in bins[:-1]],
      edgecolor="white", linewidth=.3)
a.axvline(HALF + .5, color=INK, lw=2.0, ls="--")
a.text(HALF + 1.5, frac.max() * .55, "fifty opens", fontsize=14, color=INK)
a.set_ylim(0, frac.max() * 1.30)
a.text(24, frac.max() * 1.10, f"everyone lives · {100*(longest<=HALF).mean():.0f} per cent",
       fontsize=19, color=TEAL, weight="bold", ha="center")
a.text(79, frac.max() * 1.10, f"nobody does · {100*(longest>HALF).mean():.0f} per cent",
       fontsize=19, color=AMBER, weight="bold", ha="center")
a.set_xlabel("length of the longest cycle", fontsize=14)
a.set_ylabel("share of nights", fontsize=14)
a.set_xlim(0, N + 1)
for sp in ("top", "right"):
    a.spines[sp].set_visible(False)
plt.tight_layout(pad=1.4)
fig.savefig("fig_2.png", dpi=150, bbox_inches="tight", facecolor="white")

**Figure 1.** Two shuffles, with one bar per cycle. On the left the longest cycle has thirty-eight boxes in it and every prisoner finds his name. On the right a single cycle of seventy-eight crosses the fifty-open limit, and every prisoner on it fails together.

The Whole Answer, in One Picture

Once you see the cycles, the answer stops being about a hundred prisoners at all. It is about one number: the length of the longest cycle in that night’s shuffle. If it is fifty or under, every prisoner finds his name. If it is longer, everyone on that cycle fails, and so does the room.

**Figure 2.** The length of the longest cycle over two hundred thousand shuffles. Everything left of the fifty line is a night the whole room survives; the tail to the right is what kills them, and it is fat.

Where the Thirty-One Per Cent Comes From

The probability that a random permutation of $n$ items has a cycle longer than $n/2$ is a sum you can write down. A cycle of length $k > n/2$ is unique when it exists, and the number of permutations containing one is $\binom{n}{k}(k-1)!\,(n-k)!$, which simplifies beautifully:

$$\Pr\!\left[\text{longest cycle} > \tfrac{n}{2}\right] \;=\; \sum_{k=n/2+1}^{n} \frac{1}{k} \;=\; H_n – H_{n/2}.$$

$(2)$

For a hundred prisoners that is $H_{100} – H_{50} = 0.6882$, so the strategy succeeds with probability $0.3118$. Two hundred thousand simulated nights gave $0.3100$.

And as the room grows, the harmonic difference converges to a constant everybody recognises:

$$\lim_{n \to \infty} \left(H_n – H_{n/2}\right) \;=\; \ln 2 \qquad\Longrightarrow\qquad p_\infty \;=\; 1 – \ln 2 \;=\; 0.3069.$$

$(3)$

A thousand prisoners, a million prisoners: still about thirty-one per cent. The strategy does not decay with the size of the room, which is the part that ought to feel impossible.

What to Carry Away

The strategy did not make any individual prisoner luckier. Each one still opens fifty of a hundred boxes and still has an even chance of finding his name. The marginal probability for each prisoner is unchanged at one half.

What changed is the dependence. Under random opening, a hundred roughly independent coin flips must all land right. Under the cycle strategy, the hundred outcomes are welded to a single underlying quantity, and there is only one thing left to go wrong. Instead of a hundred chances to fail, the room has one.

That is the transferable lesson, and it has nothing to do with prisoners. When a system must survive many simultaneous events, the correlation between them matters more than any individual probability. Engineering the dependence is often available when improving the individual odds is not, and it can buy factors that no amount of local effort could.

A factor of four times ten to the twenty-nine, in this case, from a rule that fits in one sentence.

Interested in applying these ideas to your work? Get in touch.