Skip to Main Content
HBS Home
  • About
  • Academic Programs
  • Alumni
  • Faculty & Research
  • Baker Library
  • Giving
  • Harvard Business Review
  • Initiatives
  • News
  • Recruit
  • Map / Directions
Faculty & Research
  • Faculty
  • Research
  • Featured Topics
  • Academic Units
  • …→
  • Harvard Business School→
  • Faculty & Research→
Publications
Publications
  • 2021
  • Article
  • Electronic Journal of Combinatorics

Prisoners, Rooms, and Lightswitches

By: Daniel M. Kane and Scott Duke Kominers
  • Format:Electronic
ShareBar

Abstract

We examine a new variant of the classic prisoners and lightswitches puzzle: A warden leads his n prisoners in and out of r rooms, one at a time, in some order, with each prisoner eventually visiting every room an arbitrarily large number of times. The rooms are indistinguishable, except that each one has s lightswitches; the prisoners win their freedom if at some point a prisoner can correctly declare that each prisoner has been in every room at least once. What is the minimum number of switches per room, s, such that the prisoners can manage this? We show that if the prisoners do not know the switches’ starting configuration, then they have no chance of escape—but if the prisoners do know the starting configuration, then the minimum sufficient s is surprisingly small. The analysis gives rise to a number of puzzling open questions, as well.

Keywords

Mathematical Methods

Citation

Kane, Daniel M., and Scott Duke Kominers. "Prisoners, Rooms, and Lightswitches." Electronic Journal of Combinatorics 28, no. 1 (2021).
  • Read Now

About The Author

Scott Duke Kominers

Entrepreneurial Management
→More Publications

More from the Authors

    • January 12, 2023
    • a16zcrypto.com

    Progressive Decentralization: A High-level Framework

    By: Jad Esber and Scott Duke Kominers
    • December 7, 2022
    • Harvard Business Review Digital Articles

    Why Decentralized Crypto Platforms Are Weathering the Crash

    By: Shai Bernstein and Scott Duke Kominers
    • Winter 2022
    • Oxford Review of Economic Policy

    Distributing a Billion Vaccines: COVAX Successes, Challenges, and Opportunities

    By: Eric Budish, Hannah Kettler, Scott Duke Kominers, Erik Osland, Canice Prendergast and Andrew A. Torkelson
More from the Authors
  • Progressive Decentralization: A High-level Framework By: Jad Esber and Scott Duke Kominers
  • Why Decentralized Crypto Platforms Are Weathering the Crash By: Shai Bernstein and Scott Duke Kominers
  • Distributing a Billion Vaccines: COVAX Successes, Challenges, and Opportunities By: Eric Budish, Hannah Kettler, Scott Duke Kominers, Erik Osland, Canice Prendergast and Andrew A. Torkelson
ǁ
Campus Map
Harvard Business School
Soldiers Field
Boston, MA 02163
→Map & Directions
→More Contact Information
  • Make a Gift
  • Site Map
  • Jobs
  • Harvard University
  • Trademarks
  • Policies
  • Accessibility
  • Digital Accessibility
Copyright © President & Fellows of Harvard College