Problem #23 HARD
The Number-Matching Escape
Google Netflix Probability Combinatorics
Problem Statement
A warden has 100 prisoners, each assigned a unique ID from 1 to 100. In a challenge room, there are 100 closed boxes numbered 1 to 100. Inside each box is a slip of paper with one prisoner ID — all 100 IDs are distributed, one per box, in a secret random arrangement. Each prisoner enters the room alone, may open at most 50 boxes, must leave everything as found, and cannot communicate with those who go after them. All 100 must find their own ID slip. If everyone succeeds, they all go free. They may discuss strategy beforehand. What strategy maximizes their collective survival odds, and what is that probability?
Answer & Quick Explanation
Think you've got it? Click below to check your answer.
Follow the cycle: open your own-numbered box, then follow the ID chain. Collective success probability ≈ 30.7%. The strategy works because all prisoners share the same permutation structure, turning independent near-zero odds into a joint 31% chance.
Detailed Editorial Solution
Want to see the step-by-step breakdown? Click below to reveal the editorial.
The 100 boxes hold a permutation of the IDs 1–100. Any permutation decomposes into disjoint cycles. The chain-following strategy is guaranteed to find a prisoner's own ID within at most as many steps as the length of the cycle their ID belongs to.
Step 1: Prisoner n opens box n. If the slip says k, they next open box k. They continue until they find their own number n, or until they've opened 50 boxes.
Step 2: This strategy always works for a prisoner if and only if their ID is part of a cycle of length 50 or fewer in the secret permutation.
Step 3: The strategy fails for everyone if any single cycle in the permutation has length greater than 50 — because at least one prisoner's chain would exceed 50 steps.
Step 4: Probability of failure = probability that the random permutation contains at least one cycle longer than 50 = (1/51) + (1/52) + ... + (1/100).
Step 5: This sum equals approximately ln(100) − ln(50) = ln(2) ≈ 0.693. So P(failure) ≈ 69.3%.
Step 6: P(success) ≈ 30.7% — compared to (1/2)^100 ≈ 10^−30 for random guessing. An astronomically better outcome.
Key Insight:
The strategy creates a collective correlation: either all prisoners in a long cycle fail together, or all succeed. By coupling their fates through shared cycle structure, the group trades many independent 50% risks for one shared 31% chance — a vastly better deal.