100 Prisoners, Hats, and Light Bulbs: Classic Quant Brainteasers

A handful of brainteasers come up so often in quant-trading interviews that they have their own names. The “100 prisoners and the boxes” puzzle, the “hats on prisoners” line of problems, and the “100 prisoners and a light bulb” puzzle are interview classics at Jane Street, Optiver, SIG, Citadel Securities, Akuna, IMC, and most market-making firms. They’re not asked because the firms expect you to have heard them — they’re asked because the structure rewards a specific kind of thinking that maps to trading: spotting hidden symmetry, finding clever group strategies, and reasoning about information flow under constraints.

This guide walks through each of the three classics, explains the elegant solution, and shows the meta-pattern behind why these problems work the way they do.

Problem 1: 100 Prisoners and the Boxes

Setup

100 prisoners are numbered 1 to 100. In a separate room, there are 100 boxes, also numbered 1 to 100. Inside each box is a slip of paper with a prisoner’s number on it; each prisoner’s number appears in exactly one box, and the placement is a uniformly random permutation. Each prisoner enters the room one at a time and may open up to 50 boxes. They must find their own number. They cannot communicate once the process starts, and they cannot rearrange the boxes. If every prisoner finds their number, all 100 are freed; if any prisoner fails, all 100 are executed.

Question: Is there a strategy that gives the prisoners a non-trivial chance of survival? What’s the probability of survival under that strategy?

The naive answer

If each prisoner picks 50 boxes at random, each has a 1/2 chance of finding their number. The chance of all 100 succeeding is (1/2)^100, which is astronomically small. So at first glance, the prisoners are doomed.

The clever strategy

Each prisoner uses the following procedure: open box number equal to your own prisoner number first. Read the slip inside. Then open the box numbered to match the slip you just read. Continue following the chain — each slip points to the next box to open — until you either find your own number (success) or open 50 boxes (failure).

Why it works

The random placement of slips defines a permutation of {1, …, 100}. Permutations decompose into cycles. The strategy follows the cycle containing the prisoner’s number. The prisoner finds their number if and only if the cycle containing them has length ≤ 50.

All prisoners succeed if and only if every cycle in the permutation has length ≤ 50. Equivalently: no cycle has length > 50. Since a permutation of 100 elements has at most one cycle of length > 50 (otherwise two cycles would each contain more than half the elements, which is impossible), the failure condition reduces to: at least one cycle of length > 50 exists.

The probability that a random permutation of 100 elements has a cycle of length > 50 is:

P(failure) = ∑(k=51 to 100) 1/k = 1/51 + 1/52 + … + 1/100 ≈ ln(100) – ln(50) = ln(2) ≈ 0.693

Therefore P(success) ≈ 1 – 0.693 = 0.307, or about 30%.

What interviewers want

Don’t worry about computing the harmonic-tail probability exactly — the interviewer cares whether you (a) recognize that random selection gives (1/2)^100, (b) realize there must be a clever group strategy, (c) describe the cycle-following procedure, and (d) reason about why it depends on permutation cycle structure. If you get to “the answer is roughly ln(2)” that’s a strong signal.

Problem 2: Hats on Prisoners

Setup (basic version)

N prisoners stand in a line. Each wears a hat that is either red or blue, randomly. Each prisoner can see all hats in front of them but not their own and not behind. Starting from the back of the line, each prisoner must call out a guess for the color of their own hat. If they’re right, they live; if wrong, they die. Each prisoner hears all previous guesses. Before the game starts, the prisoners may agree on a strategy. What’s the optimal strategy?

Solution

The first prisoner (at the back) calls out the parity of red hats they see in front of them: “red” if they see an odd number of red hats, “blue” if even. They have a 50/50 chance of being right (about their own hat).

Every subsequent prisoner can deduce their own hat color exactly. They know the parity of red hats among the N-1 hats in front of the first prisoner (because the first prisoner announced it). They can count red hats among the prisoners ahead of them, and they’ve heard guesses from prisoners between them and the first prisoner. With this information they can solve for their own color exactly.

Result: All N-1 prisoners after the first survive with certainty. The first prisoner has 1/2 survival probability. Total expected survivors: N – 1/2.

Variations

K colors instead of 2: Generalize parity to “sum modulo K.” First prisoner announces sum-mod-K of all hats they see. Same logic; all subsequent prisoners survive.
Cannot hear previous guesses: Much harder. Best you can do is guarantee N/2 survivors (pair them up: prisoner 2k+1 announces hat color of prisoner 2k).
Infinite prisoners with axiom of choice: Strange measure-theoretic puzzle; only finitely many prisoners die. Outside the scope of standard interviews but sometimes mentioned.

Problem 3: 100 Prisoners and a Light Bulb

Setup

100 prisoners are kept in solitary cells. There’s a single common room with a light bulb (initially off). Each day, the warden randomly selects one prisoner (uniformly, with replacement) and brings them to the common room. The prisoner can choose to flip the light switch (on→off or off→on) or leave it alone. The warden returns them to their cell. At any point, any prisoner may declare “every prisoner has visited the common room at least once.” If they’re right, all are freed; if wrong, all are executed.

The prisoners may agree on a strategy beforehand but have no further communication. Find a strategy that guarantees eventual freedom.

Solution: counter strategy

Designate one prisoner as the “counter.” All other prisoners follow this rule:

If you enter the room and the light is OFF, and you’ve never turned it on before, turn it ON. Otherwise leave it.
If you enter the room and the light is ON, leave it.

The counter follows this rule:

If you enter the room and the light is ON, turn it OFF and increment your internal count by 1.
If you enter the room and the light is OFF, leave it.
When your count reaches 99, declare that all prisoners have visited.

Why it works

Each non-counter prisoner turns on the light exactly once across all their visits. Each time the counter sees the light ON, it represents a unique non-counter prisoner who has visited the room at least once. When the counter has reset the light 99 times, all 99 non-counter prisoners have visited (and the counter has obviously visited themselves, since they’re the one counting).

Variations

Light bulb starts in unknown state: Counter waits for the first ON before counting, or each non-counter turns on the light twice instead of once. Counter then needs to see 198 ON states.
Question is “has every prisoner visited at least twice?”: Each non-counter turns on the light twice; counter needs to see 198 ON states.

The Meta-Pattern

All three classics share a structural feature: a problem that looks impossibly hard, where the right answer comes from finding a clever group strategy that uses limited communication channels in non-obvious ways.

Boxes problem: the strategy is “follow the cycle,” and the analysis comes from cycle structure of random permutations.
Hats problem: the strategy uses parity (sum mod K) as a single-bit communication channel that gets all subsequent prisoners “for free.”
Light bulb problem: the strategy uses the light as a single-bit communication channel between non-counters and a designated counter.

Strong candidates spot the structural similarity: each problem has a clever encoding that turns a seemingly random situation into a deterministic one. Articulating that meta-insight, even briefly, is a strong signal. It says: “I see the pattern, not just the solution.”

Frequently Asked Questions

Are these problems still asked? They feel like classics.

Yes, frequently. They’re “classics” in the sense that interviewers and candidates both know them, but interviewers ask them anyway because they’re useful diagnostics. The interviewer often expects you’ve at least heard of one or two and is interested in how clearly you can explain the solution and reason about variations. If you’ve heard the problem, say so honestly; the interviewer will pivot to a variation or a follow-up. Pretending you haven’t heard it and stumbling through is worse than admitting it.

What if I haven’t seen these before and the interviewer asks one?

Reason out loud. For the boxes problem, point out (1/2)^100 is impossibly small, so there must be a clever strategy; then think about cycle structure. For hats, recognize the first prisoner sacrifices to communicate one bit. For light bulbs, look for ways to encode “I visited” using the only available channel. Most interviewers will give you 10–15 minutes and offer hints if you’re stuck; they care about your reasoning more than whether you arrive at the answer unaided.

Why do market makers care about these?

The puzzles probe several skills market makers value: spotting hidden structure (cycle decomposition, parity, single-bit channels), reasoning under constraints (limited communication), thinking in expectation (1/2 probability for the boxes problem first prisoner, 30% for the cycle strategy), and articulating clever non-obvious strategies. These map directly to trading: spot non-obvious structure in markets, reason about flow under constraints, and design clever strategies that outperform naive baselines.

What’s the hardest variation I should expect?

For the boxes problem: “what if prisoners are allowed to open 70 boxes instead of 50?” (Answer: probability of success rises sharply; compute the harmonic-tail sum.) For hats: “what if there are 3 colors and prisoners can’t hear previous guesses?” (Much harder; pair-up strategies, partial guarantees.) For light bulbs: “what if the bulb’s initial state is unknown?” (Counter waits for first ON or each prisoner turns the light on twice.) Strong candidates think through 1–2 variations even after solving the base case — this signals depth.

How important are these specifically vs other brainteasers?

Important but not unique. These three are among the most-asked named puzzles, but interviewers have hundreds of brainteasers in rotation. The skill is general: clever group strategies, clean probability reasoning, articulation under pressure. Practicing these three teaches you the meta-skill that transfers to puzzles you’ve never seen. See our broader Probability Brainteasers guide for more.