论文标题
囚犯，房间和灯光开关
Prisoners, Rooms, and Lightswitches
论文作者
论文摘要
我们检查了经典囚犯和灯光开关难题的一种新变体：一名看守带领他的$ n $囚犯进入$ r $ $房间，一次是一个顺序，每个囚犯最终都会访问每个房间的每个房间。房间是无法区分的，除了每个房间都有$ s $ lightswitches；如果囚犯在某个时候可以正确宣布每个囚犯至少一次在每个房间里，囚犯赢得了自由。每个房间的最小开关数量是多少，$ s $，以便囚犯可以管理这一点？我们表明，如果囚犯不知道Switches的起始配置，那么他们就没有逃脱的机会 - 但是，如果囚犯确实知道起始配置，那么最低限度的$ S $就很小。该分析也引起了许多令人困惑的开放问题。
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.
