We examine a new variant of the classic prisoners and light switches 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$ light switches; 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.
@article{10_37236_9905,
author = {Daniel M. Kane and Scott Duke Kominers},
title = {Prisoners, rooms, and light switches},
journal = {The electronic journal of combinatorics},
year = {2021},
volume = {28},
number = {1},
doi = {10.37236/9905},
zbl = {1475.91007},
url = {http://geodesic.mathdoc.fr/articles/10.37236/9905/}
}
TY - JOUR
AU - Daniel M. Kane
AU - Scott Duke Kominers
TI - Prisoners, rooms, and light switches
JO - The electronic journal of combinatorics
PY - 2021
VL - 28
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/9905/
DO - 10.37236/9905
ID - 10_37236_9905
ER -
%0 Journal Article
%A Daniel M. Kane
%A Scott Duke Kominers
%T Prisoners, rooms, and light switches
%J The electronic journal of combinatorics
%D 2021
%V 28
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/9905/
%R 10.37236/9905
%F 10_37236_9905
Daniel M. Kane; Scott Duke Kominers. Prisoners, rooms, and light switches. The electronic journal of combinatorics, Tome 28 (2021) no. 1. doi: 10.37236/9905
