一百个囚犯和一盏灯

一、问题的初始版本

监狱里有100个囚犯，关在100个单独密闭的牢房里，互相不能见面和以任何方式交流。囚犯平时都一直呆在牢房内，一日定时三餐，按时起卧。每天晚饭后，典狱长会随机选出一个囚犯在监狱庭院内单独放风十分钟。每天每个囚犯都有百分之一的可能被选到做那个放风的人，和他以前的放风经历无关。

庭院里有一盏灯和控制它明灭的开关。除了囚犯，没有人会去动开关。灯很牢靠，不会坏，不会没电。庭院内（包括其中的灯）的任何动静都无法被关在牢房中的囚犯得知。

有一天典狱长发善心，把这100个囚犯聚到一起，宣布：如果某天有个囚犯报告说，所有囚犯都至少放过一次风（从宣布规定后的次日算起），而且的确如此，那么所有囚犯都将被立即释放；但如果其实并非如此，所有囚犯会被立即处决。

现在众囚犯可以在一起商量一个对策，然后就又会恢复到以前不能见面和交流的状态。

假设所有囚犯都渴望被释放，但都不想冒哪怕是一丝被处决的风险（也即如果有人报吿说所有囚犯都已放过风，那么他必定能以严谨的逻辑证明他的结论正确，而不是基于某种概率上的考虑）。我们可以假设囚犯们是永生的（典狱长也如此），这也解释了为什么他们不想冒一丝被处决的风险。囚犯能够改变的唯一的庭院状态就是灯的明灭（不许做任何其他记号）。

是否有在足够长时间后囚犯必被释放的方案？

二、初始版本问题的简单解法

题目里没有说明灯最初是开着的还是关着的。但这并不要紧，可以规定第一天无论是谁放风，都将灯关掉，而约定的方案从第二天开始执行。所以我们可以假定最初灯就是关着的。

事先选定一个囚犯做计数人，他负责记住一个数，这个数最开始是0。轮到他放风时，如果灯是关的，那么就什么也不做；如果灯是开的，那么关掉灯，并将记住的数字加1。当这个数字达到99时，就向典狱长报告所有人都已放过风。

其他囚犯在轮到放风时，如果灯是开的则什么都不做；如果灯是关的，而且以前他从来没有开过灯，那么就开灯；否则就什么也不做。

容易看出在这个方案下，只要经过足够长的时间，每个不是计数人的囚犯都会开且仅开一次灯，而这次开灯必会被计数人发现并关灯。所以这是一个足够长时间后囚犯们必被释放的方案。

三、进阶版问题

如果典狱长提出的要求不是某个囚犯宣布所有人都放过风，而是要说出更复杂的信息呢？我们把题目改一下。

在囚犯聚集开会时，典狱长宣布的是如下规则：
1) 等一下回牢房里，每人都会发现牢房墙上写有一个大于0小于100的自然数（每人牢房内的数字并不一定是独一无二的）。
2) 如果某天有个囚犯说出所有这100个牢房内的数字之和，那么所有囚犯都将被立即释放；但如果数字错误，所有囚犯会被立即处决。

其他情况同原题。

四、求和问题的解法

观察原问题条件我们可以发现，囚犯通过每日的日程（一日三餐和睡觉），能够计算日子的流逝。这是除了开关灯外的第二个传送信息渠道。

我们仍可假设最初的灯是关着的。

我们把日子分割成每1000000日为一个循环，就像我们日常的星期是每七天一个循环。和“星期一”、“星期二”……这些名字类似，按照日子在循环里的位置，我们将它们分别命名为“循环日1”、“循环日2”……“循环日1000000”，循环日1000000以后的那天就是新的循环日1。规定聚会的次日也即第一天是循环日1。

每个囚犯要注意计算每天是循环日几（只要把前一天的数字加1即可，而且记得循环日1000000以后的那天是循环日1）。他还要记住一个数字，这个数字最初是他牢房里写的数字加上10000（比如他牢房里的数字是12，就记住10012）。放风时的任务如下：
1) 如果灯是开着的，那么关掉灯。把记住的数字和当日名字里的数字相加再减1，变成新的要记住的数字（比如记住的数字是10012，当天是循环日661234，那么就关掉灯，记住10012+661234-1，也即671245）。当记住的数字超过1000000，就向典狱长报告记住的数字的最后四位（比如记住的是1007890，就报告所有数字和为7890）。
2) 如果灯是关着的，而且放风那天的名字恰好和他记住的数字一致（比如他记住的是661234，而放风的那天恰好是循环日661234），那么打开灯，把记住的数字变成0。
3) 否则什么也不做，也不改变记住的数字。

直观地看，这是利用日子名字来不断地合并囚犯牢房中的数字信息：如果一个囚犯记住的数是453333，这意味着他的数字已经合并了45个囚犯牢房中的数，它们的和是3333。当最终有囚犯得到100abcd这样的数时，他就知道自己已经合并了所有100个囚犯的信息，其和为abcd。

下面严格证明这个方案可行。

首先容易看出，如果一个囚犯放风时发现灯是亮的，那么一定是前一天放风的囚犯开的。

我们把囚犯和灯统称为“赋值物”，并按如下方式给它们赋值：令每个囚犯的“值”为他记住的数。而庭院里的灯的“值”，如果是关的话为0，如果是当天被某囚犯开的，其值为当天名字里的数字，如果是前一天被开的，为当天名字里的数字减1。在最开始，所有赋值物的值的和（也就是所有囚犯的值的和，因为最初灯是关的，值为0），是一个形如100abcd的数字，其中最后四位数abcd即所求的所有牢房里数字之和。任何99个囚犯的最初值加起来都不会大于1000000，因为每人的初值都小于10100。

首先，我们注意到，上述方案中囚犯任务的三种情况和日子的流逝，都不会改变这个和值：
1) 如果灯是开着的，关掉灯会让灯值清零，也即少掉了当日名字中的数字减1，但是马上这个少掉的数字就被加到关灯囚犯记住的数里。
2) 如果灯是关着的，而且放风那天的名字恰好和放风囚犯记住的数字一致，囚犯会打开灯，于是灯值会增加放风囚犯记住的数字，而囚犯值也即他记住的数会清零。
3) 如果灯是关着的而囚犯什么也没做，和值当然不变。
4) 如果当天不是循环日1000000，而且此日囚犯打开了灯，过一夜后日子数字加1，但是灯值不变。
5) 循环日1000000放完风后的灯一定是灭的，不会有囚犯在循环日1000000那天打开灯，因为没人会需要记住1000000这个数（这意味着100个牢房内的数字加起来等于0），所以从循环日1000000转到循环日1的那天晚上不会改变和值。

其次，值非0的赋值物数目只会减少，不会增加。
1) 上述方案的放风过程三种情况下，灯的值变非0时囚犯的值必变0，囚犯的值变非0时灯的值必变0。所以值非0的赋值物数目不会增加。
2) 如果至少有两个囚犯P和Q记住的数非0，那么总存在这种可能性（尽管很小），囚犯P恰好在和他记住的数字一致的那天放风，那天的灯是关的，而囚犯Q恰好在次日放风。于是此后囚犯P记住的数字为0，而囚犯Q则记住了原来两人值之和。这就让值非0的赋值物数目少了1。

总而言之，足够长的时间以后，会出现只有一个赋值物有非0值的情况，这个赋值物是一个囚犯，他发现他的值也即他记住的数字是100abcd。此时他会向典狱长报告abcd，使得所有囚犯获释。

五、交换更多的信息

上面这个方案里，囚犯们不断地用和的形式来合并各自的信息。检查一下方案和其证明就能发现，用类似的方案，同样可以将信息以积的形式来合并。但是积（以及整数的唯一因子分解）的计算比较复杂，我们在此假设囚犯的数学和逻辑能力超群，并且有无穷的计算和储存能力：任意大的具体整数之间的加减乘除都能在瞬间完成，而且可以在瞬间完成任意有限次的上述加减乘除；所有的计算结果都能保存下来。

假如囚犯们知道每个牢房里的数字都是素数，而且都小于某具体的自然数N。那么他们就知道所有数字的乘积小于N¹⁰⁰。只要把日子改为N¹⁰⁰日一循环，我们就能制定出以积的形式来合并信息的方案。在这个方案中，不需要和形式方案中万位以上用来表示已合并的数字个数的“加上10000”部分。因为所有最初的数都是素数，所以只要把手上的自然数唯一因子分解一下，看其中有几个素因子，就知道有多少条数字信息被合并了。

具体方案如下：

每个囚犯要注意计算每天是循环日几。他还要记住一个数字，这个数字最初是他牢房里写的素数。放风时的任务如下：
1) 如果灯是开着的，那么关掉灯。令当日名字里的数字为A，把记住的数字乘以(A-1)，变成新的要记住的数字。当记住的自然数的唯一因子分解中的素因子个数等于100，这些素因子就是100个牢房里的那些素数。
2) 如果灯是关着的，而且放风那天的名字恰好和他记住的数字一致，那么打开灯，把记住的数字变成1（注意这里是1而不是0，因为我们使用乘法而不是加法）。
3) 否则什么也不做，也不改变记住的数字。

证明同和形式方案类似。

六、素数可以表示任意数

上面这个积形式方案的优点在于，通过自然数的唯一因子分解，最终知道的是每一个囚犯牢房中的数字也即具体的原始信息；而不是象和形式方案中得知的那样，是所有数字的和这样已被整合过的信息。

也许有人会说，积形式方案增加了每个数必须是素数的要求。如果每个囚犯手里的数并非素数，岂不是不能用这个方案了？

并非如此。把所有素数从小到大排成（无穷的）一列：
2, 3, 5, 7, 11, 13, 17, 19, ……
如果囚犯手里的数是A，他就选取第A个素数来表示A。比如手里的数是2，那么就选取3，如果手里数是5，就选取11……知道原来数字的上限，就能知道被选取的这些素数的上限，然后就能使用积形式方案交换并得到所有100个素数。通过这些素数，反过来也就能知道原来的数字是多少了。

而在如今的数字化世界中，所有信息都可以被一个自然数所表达：一张照片，一首歌，一部电影，都是一个二进制文件，也就是一个（也许很大的）自然数。所以，就算典狱长给每个囚犯一部保存在蓝光碟上的电影，要求最后有个囚犯能给出所有囚犯的电影，囚犯们也能在足够长的时间里，仅通过一盏灯，做到这一点。

七、初始版本问题的小变动

上面讨论的积形式方案无疑是强大的。但是它基于一个重要的条件：每个囚犯在放风时能够知道那天是什么日子，或更一般地，知道自己某次放风时，已经进行过的放风次数。如果没有这个条件（比如说如果牢房里的生活并不是非常有规律，以至于无法判断两次放风之间过去了几天，或是典狱长并不是固定每天放风一人，而是有可能一天放风好几人，或是好几天都不放风一人），那么他们就无法通过日子名字中的数字来互相交换信息，于是也就不可能实行此方案。

但是第二节中初始版本问题的简单解法并不基于日子来交换信息，所以即使在无法判断放风那天是什么日子的情况下，也还是可以进行。唯一的难点在于，如果不知道最初的灯是开还是关，计数人在关掉99次灯时会遇到一个疑惑：如果最初的灯是开着的，那么这99次关灯中，其实他关过一次并不是由某囚犯打开的灯，也就是有一个囚犯还没有打开过灯，此人也许从来没有放过风。

这个难点可以很容易地解决。只要规定，除了计数人以外的其他囚犯都要开两次灯，而计数人在计数到198时才报告所有人都已放过风。