The Light Switch Protocol

Question

100 prisoners are held in isolation. Each day the warden takes one uniformly random prisoner into a room containing a single light switch (initially OFF, and everyone knows it), which the visitor may leave as-is or toggle. At any time, any prisoner may declare "all 100 of us have visited the room." A correct declaration frees everyone; an incorrect one is fatal. Design a strategy that succeeds wit

Accepted Answer

The counter protocol. Before starting, designate one prisoner the counter. - Non-counter rule: if the switch is OFF and you have never turned it on before, turn it ON. Otherwise touch nothing. - Counter rule: if the switch is ON, turn it OFF and add 1 to a private tally. When the tally reaches 99, declare. Correctness: the switch being ON means exactly one not-yet-counted non-counter has signaled (each signals at most once in their life; nobody else ever turns it on). Every OFF→ON is matched by exactly one counter increment, so a tally of 99 proves 99 distinct non-counters have visited, plus the counter makes 100. The declaration can never be premature, and it eventually happens because every prisoner visits infinitely often with probability 1: every un-signaled prisoner eventually meets an OFF switch. Cost: each of the 99 signals must be "collected" by the counter before the next can be lodged, a token-passing bottleneck through one agent. Simulation puts the mean at roughly 10,400 days ≈ 28½ years: about 100 days per collection cycle (waiting for the counter) dominates, plus a coupon-collector tail waiting for the last few un-signaled prisoners to find the switch OFF. What's bein

The Light Switch Protocol

Problem

Your answer

Hints

More Brainteasers & Logic to train on