22 名囚犯与两盏开关：如何保证获释？
How do the prisoners guarantee their freedom?
题目详情
有 22 名囚犯分别关在 22 个牢房。典狱长说他会每天随机带 1 名囚犯进入一个房间，房间里有两个开关，初始都处于向下（关）的位置，被带进去的囚犯可以拨动开关。
只要有人能向典狱长正确宣布“所有囚犯都至少进过一次房间”，就可以全部获释；若宣布错误则全部处死。
囚犯们有 1 小时讨论策略，之后再无任何交流。
问：如何保证最终一定能获释？
There is a prison of 22 prisoners in 22 cells. The warden says to them he will take them into a room with two light switches, which willeach begin in the down position, and the prisoner may use a switch. However hewill take them randomly, one a day. The warden says that as soon as anyone can tell him that all the prisoners have been into the room he will let them free, but if they get it wrong they hang. He gives them one hour to discuss their strategy, and after that there will be no communication. How do the prisoners guarantee their freedom?
解析
选定 1 名“计数者”，只使用其中一个开关（另一个始终不动保持关闭）。
约定用左开关表示信号：
-
21 名非计数者：在自己一生中第一次进入房间且看到左开关为“关”时，把它拨到“开”，并且从此以后无论何时进入都不再碰任何开关；若看到已是“开”，则什么也不做。
-
计数者：每次进入房间，若看到左开关为“开”，就把它拨回“关”，并把计数加 1；若为“关”，则什么也不做。
当计数者的计数达到 21 时，他就可以安全宣布：每个非计数者都至少把开关从关拨到开过一次，因而每个人都至少进过房间一次。
该策略保证正确性（不会误报），并且在随机抽取下最终一定会达到 21 次计数，因此保证获释。