100 prisoners, one light bulb.
The 100 prisoners and a light bulb puzzle: prisoners visit a room one at a time in random order, may toggle a single bulb, and must eventually prove everyone has visited. One bit of shared state, no communication otherwise. The classic solution is a counter, and it takes decades.
One hundred prisoners are held in solitary cells. There is a room with one light bulb and its switch. The bulb starts off. Each day the warden picks a prisoner uniformly at random (the same prisoner may be picked on consecutive days) and takes them to the room, where they may leave the bulb as it is or toggle it. Then they return to their cell. Nobody else can see the room.
At any time, any prisoner in the room may declare "all 100 of us have now been in this room." If the declaration is true, everyone is freed. If it is false, everyone is executed. Before the process starts, the prisoners meet once and may agree on any strategy.
Devise a strategy that guarantees a correct declaration eventually. Then estimate how long it takes.
The constraints are severe on purpose. The bulb is a single bit of shared memory, the prisoners have no clock beyond their own visits, and a prisoner cannot tell how many days have passed since their last visit. Whatever the strategy is, it has to be robust to one prisoner being picked twenty times before another is picked once. Start by asking what one bit can possibly communicate, and to whom.
Stuck? Open hints one at a time
Each hint gives away one more layer. Stop the moment something clicks.
Hint 1 a nudge
Symmetric strategies, where everyone plays the same role, struggle because one bit cannot count to 100. Break the symmetry: appoint one prisoner to a special role before the process begins.
Hint 2 the key move
Make the bulb a message from "some new prisoner has visited" to the appointed counter. Each non-counter should send that message exactly once in their lifetime, and only when the channel is free.
Hint 3 nearly the answer
Non-counter rule: if the bulb is off and you have never turned it on, turn it on; otherwise do nothing. Counter rule: if the bulb is on, turn it off and add one to a tally. What tally proves everyone has visited?
The solution
Reveal the full solution
Appoint one prisoner as the counter. Everyone else follows one rule: on entering the room, if the bulb is off and you have never switched it on before, switch it on; in every other case, leave it alone. The counter follows the complementary rule: if the bulb is on, switch it off and add one to a private tally. When the tally reaches 99, the counter declares.
Correctness rests on the bulb being a one-slot mailbox. A non-counter posts a message ("someone new was here") by turning the bulb on, and does so exactly once in their lifetime; the counter collects each message by turning the bulb off. Messages cannot be lost, because a non-counter who finds the bulb already on simply waits for a later visit, and cannot be duplicated, because each non-counter posts at most once. So the tally equals the number of distinct non-counters who have visited, and 99 means all of them. The counter has obviously visited too. The declaration can never be false.
It is also slow. Each message needs two events, a non-counter posting it and the counter collecting it, and the counter is picked only one day in a hundred on average. Early on, new prisoners arrive quickly; late in the process the last few unposted prisoners are rare draws, and every message waits for a counter visit before the mailbox frees up. Working through the expectation gives on the order of ten thousand days, roughly 28 years. That figure surprises people, and it is the honest answer: the single-counter strategy is correct, but it is not fast.
What this puzzle is really testing
Protocol design under a brutally narrow channel. The solution assigns roles, defines a message, and guarantees delivery without acknowledgement, using a bit of shared state as a lock; it is a mutex and a counter built from one flag. Engineers who have reasoned about a single shared variable between threads will recognise the shape, and the state design template shows the same discipline, "what exactly does this state encode", applied to dynamic programming. The counting logic is a tiny relative of the seen-so-far pattern: track what has been observed, never re-count it.
Follow-ups to expect
The bulb's initial state is unknown. Then a spurious first message is possible, so have every non-counter post twice and let the counter declare at a tally of 198: if the bulb started on, the phantom plus 197 real messages still forces all 99 to have posted at least once, and if it started off, 198 means everyone posted twice. Can it be made faster? Yes, with staged protocols where several assistant counters accumulate messages in batches and later hand them up, which cuts the expected time by roughly a factor of three at the cost of a much more intricate rule set. Interviewers usually stop after the counter, but they enjoy hearing that you know the counter is not the end of the story.