Prisoners, Rooms, and Lightswitches

Daniel M. Kane, Scott Duke Kominers

Abstract

This paper generalizes the classic "one-bulb room" prisoner puzzle to a multi-room, multi-switch environment. In the Prisoners, Rooms, and Lightswitches (PRL) problem, $n$ prisoners must determine when every individual has visited every one of $r$ indistinguishable rooms. The authors investigate the minimum number of switches $s$ required per room to solve this coordination challenge. They prove that while no solution exists if the initial switch states are unknown, two switches per room (four configurations) are sufficient to guarantee freedom for any number of prisoners and rooms. Conversely, they demonstrate that one switch is insufficient for five or more rooms, establishing a fundamental lower bound on the state space required for distributed coordination in this setting.

Introduction

The classic "One-Bulb Room" puzzle is a staple of recreational mathematics: $n$ prisoners are led one-by-one into a room with a single lightswitch. They must devise a strategy to eventually declare that every prisoner has visited the room at least once. The standard solution involves a designated "leader" who counts signals (switch flips) from the other prisoners.

Kane and Kominers extend this to a significantly more complex scenario: $n$ prisoners, $r$ indistinguishable rooms, and $s$ lightswitches per room. The goal is now for a prisoner to correctly declare that every prisoner has visited every room. This introduces a massive coordination problem: how do you track progress across multiple identical rooms without a global clock or direct communication? The paper investigates the minimum number of switches $s$ required to solve this PRL problem.

Methodology

The authors employ a formal algorithmic framework to describe prisoner strategies. These strategies are built from primitives such as FLIP(A, B) (wait for configuration A, then change to B), SEE(A) (wait for configuration A), and REPEAT(k). This formalization allows for rigorous proofs regarding the state-space requirements of any successful protocol.

To prove impossibility results, the authors utilize an adversarial warden approach. If the warden knows the prisoners' deterministic strategy, he can construct "indistinguishable schedules"—sequences of room visits that look identical to the prisoners but lead to different ground truths. For example, in one schedule, everyone has visited every room, while in another, they have not; if the switch configurations remain identical in both cases, the prisoners cannot distinguish between the two and may declare incorrectly.

For sufficiency proofs, the authors construct explicit protocols. They move from "naive" solutions (storing the entire visit history in binary) to more efficient "one-prisoner-at-a-time" and "one-room-at-a-time" strategies that minimize the required state space.

Key Insights and Ideas

The "Unknown Start" Impossibility

Unlike the one-room case, if there are multiple rooms and the prisoners do not know the initial switch positions, they are doomed. The warden can always hide "untouched" rooms by mimicking the starting configuration in the rooms the prisoners do visit. Without a known baseline, the prisoners can never be certain if a room is in its original state or has been modified by a peer. (Theorem 2.2)

The Power of Four States ($s=2$)

With just two switches per room (providing four possible configurations), prisoners can implement a "passing the torch" protocol. In this system, one "active" prisoner verifies they have visited every room by toggling all rooms between two states (0 and 1). Once finished, they signal the next prisoner via a "READY" state. This sequential verification ensures that by the time the leader finishes counting, every prisoner has indeed seen every room. (Theorem 3.2)

Information Bottlenecks at $s=1$

The authors prove that one switch (two states) is insufficient for $r \ge 5$. They introduce the concept of "provable ownership" of a configuration. If a prisoner hasn't visited all rooms in a certain state, they don't "own" that state's information. The warden can exploit this by reconfiguring rooms behind the prisoners' backs, preventing anyone from ever gaining enough certain knowledge to declare freedom. (Theorem 3.7)

Probability-1 vs. Deterministic Strategies

There is a subtle gap between a strategy that always works in a fixed number of steps and one that works "with probability 1" (meaning it will eventually succeed given enough visits). The authors found a 3-configuration (approx. 1.58 switches) solution that works with probability 1, even if it is not strictly deterministic in a finite timeframe.

Results Summary

Scenario Result Switch Requirement ($s$)
Unknown Start Impossible N/A
Known Start (General) Sufficient $s=2$
Known Start ($r \ge 5$) Insufficient $s=1$
Probability-1 Success Sufficient 3 configurations
$\epsilon$-Solution Possible $s=1$

The $\epsilon$-solution refers to a protocol using only 2 configurations ($s=1$) that never declares incorrectly and succeeds with some non-zero probability, though it risks getting "stuck" in a state where no further progress can be made.

Conclusion and Future Work

The research establishes that while the multi-room coordination problem is significantly harder than the single-room variant, it remains solvable with a very small constant number of switches. The most prominent gap remaining is the case of $s=1$ (one switch) for a small number of rooms ($r = 2, 3, 4$). While it is impossible for five or more rooms, the lower bounds for very small $r$ remain open.

Additionally, the authors raise questions about symmetric strategies (where all prisoners follow the exact same algorithm) and forced flipping (where a prisoner must change the state upon every visit). Whether a strictly deterministic winning strategy exists for exactly 3 configurations also remains an intriguing open question in the field of distributed coordination.

Summary updated

BibTeX
@article{kane2021prisoners,
  author = {Daniel M. Kane and Scott Duke Kominers},
  title = {{Prisoners, Rooms, and Lightswitches}},
  journal = {Electron. J. Comb.},
  year = {2021},
  doi = {10.37236/9905},
}
Figure