第一弹：/t/3960
来源：原网站依然offline；存档：https://web.archive.org/web/20190823182521/https://wiki.xkcd.com/irc/Puzzles
一 孤灯审讯室
100人被关押在一所监狱里。他们被告知，一小时后，他们都将被带到无窗、隔音的单人牢房。之后他们会被从牢房带到审讯室接受审讯，顺序随机（所以每个犯人可能被多次审讯或连续审讯）；审讯结束后再被送回单人牢房。审讯室里有一个灯泡和操作它的开关。灯最初是关闭的，但只要犯人在审讯室里，就可以随意拨动开关，狱警则不会拨动开关。单人牢房里看不到审讯室的情况；每次提审一个犯人；审讯的时间长短和数量是随机的。总之，除了电灯开关，犯人们没有办法交流。在任何时候，任何一个被审讯的犯人都可以说："每个人已经至少被审讯过一次。"如果确实如此，则所有人都会被释放。如果说错了，所有的犯人都会被处决。
-
现在，囚犯们有一个小时的时间来制定他们的策略，然后他们就会被互相隔离。他们应该制定怎么样的策略才能被释放？
-
如果不知道电灯的初始状态（开还是关），他们应该制定怎样的策略？
-
假设已知每天有且只有一次审讯。在这种情况下，是否存在更有效率的解决方案？
二 生死开箱
某监狱有100名犯人，每个囚犯都有一个从1到100的独特号码。在一个房间里，100个箱子排成一排。每个箱子里都放着一张纸片，纸片上写着1到100的数字。每个数字都只出现一次。每个犯人可以单独进入房间一次，最多打开50个箱子。他们只能看箱子里是什么数字，而不能移动纸片或箱子。一个犯人离开房间、下一个犯人进来之前，所有的箱子都会被重新关上。如果有犯人没能打开装有自己号码的盒子，所有犯人都会被处死；如果每个犯人都找到了自己的号码，那么所有犯人都将获得自由。一旦这个过程开始（即第一个犯人进入了房间），犯人之间将不允许以任何方式交流。显然，如果每个犯人随机打开50个箱子，那么所有人获得自由的概率是(1/2)^100，概率很低。
-
囚犯们可以通过什么策略来提高存活概率？
-
假设你是监狱工作人员，可以在事前与囚犯交流策略。之后你可以进入房间，检查所有的箱子，然后选择任意两张纸互相调换（最多可以调换一次）。然后，你会被送出监狱，无法与任何犯人交流，流程开始。你应该怎么做才能保证所有的犯人都能获得自由？
三 悲催的数学家们
你和另外n-1名数学家（n为有限数字）被一个邪恶的独裁者逮捕并关进了监狱。监狱是圆形的，有n个相同的无窗牢房，环绕着一个中央庭院。照明系统存在一些问题——每个牢房的电灯开关控制着顺时针方向下一个牢房的灯光。更糟的是，每天晚上午夜过后，电力只足以供应持续十分之一秒的灯光。
典狱长担心你们会用灯光来交流，所以他会经常以自己选择的方式重新安排囚犯的位置，并会打扫所有牢房以防囚犯互相留下信息。他每天都可能这样做，而且你们对他的行动将全然无知。除了牢房内部，你们看不到其他人或监狱的任何部分。你们甚至不知道有多少数学家和你们关在一起。
典狱长到你们的牢房去探望你们，并解释说，如果你们在这些防范措施下还能交流，他会认为你们都值得释放：在任何时候，任何囚犯如果认为他已经发现了有多少囚犯（即n），可以向典狱长申请释放。该囚犯将被允许进行一次猜测，如果猜对了，所有的囚犯都将被释放；但如果猜错了，所有的囚犯都将被处决。
你被选中设计一个策略，来发现囚犯的数量。你可以写一封邮件概述你的策略，典狱长会将此邮件传递给所有的囚犯。然而，你的策略必须是万无一失的，因为典狱长也会阅读你的邮件。
问题：有没有一种策略可以保证你的释放？如果有，请给出。如果没有，为什么？
四 棋盘传讯
有两个犯人，还有一个典狱长。典狱长向犯人们提出了一个挑战。他的房间里有一个8x8的棋盘和64个硬币。他将走进自己的房间，将每个硬币放在棋盘的一个方格上，且随机翻转硬币（正面或是反面）。其中一个犯人首先进入房间，典狱长会向她指出一个“魔法方格”。这个囚犯可以翻转棋盘上的一枚（仅一枚）硬币，然后离开；她也可以选择不翻转任何硬币，直接离开。接着，第二个犯人进入房间检视棋盘。如果他能正确指出“魔法方格”在哪里，则两个犯人都将获得自由。
问题：第一个犯人应该使用什么策略来确保两人都能获得自由？
