100个囚犯1盏灯

小池

当年我第一次遇到这个问题时，想了三天，没想出答案。不过后来有一个女生半小时就想出来了，让我很是汗颜。

问题是这样的：

有100个囚犯刚刚因犯罪被抓近监狱。典狱长告诉他们，从明天起，每个人都会被送进一个单独的小房间里，不能和任何别的犯人暗通音信。每一天，典狱长会随机选取一人拉到一个房间里。这个房间里只有一盏灯和它的开关，犯人可以看到灯是关的还是开的，还可以随意打开或关闭这盏灯。这个房间也叫灯泡房。

如果有一天，有一个犯人声称他确定一定以及肯定100个囚犯都到过灯泡房了，那么典狱长赦免所有犯人，但如果这个犯人搞错了，那么所有的人都会被枪毙。

典狱长给了这100个犯人讨论的时间。他们能不能达成一个“协议”（protocol）来确保成功？

初看似乎不可能。但又确实存在这样一个协议。我在网上看到了一个PDF（地址：http://www.ocf.berkeley.edu/~wwu/papers/100prisonersLightBulb.pdf），来自[wu::forums]论坛，讲的很详细，可惜是英文的。于是简要编译了一些，放在下面。

我们应该先看看一些合乎情理的假设：

1. 囚犯们可以计日；

2. 灯泡的初始状态能被设定。

其实第二个假设是第一个假设的重复。因为只要有了第一个假设，我们完全可以让第一天出来的那个人把灯泡的状态变成关（或开）。

这个问题实质上是只用一个信息位（bit）来制定一个协议。虽然公共区很小，但因为时间足够多，所以，不论人数有多少（即N有多大），我们猜测，理论上信息都是可以传递的。

方法一、幸运的一天

将100天看做一个周期，如果犯人有N个，就是N天一周期。每天都会有人进入审讯室。犯人们将按如下法则做事：

● 将灯泡的初始状态设为开（ON）

● 在周期的前99天中

⏹ 如果是第一次到灯泡房，什么都不用做。

⏹ 如果是这个周期中第二次到达灯泡房，就把灯关掉（OFF）。

⏹ 如果是这个周期中第三次来到这里，或者来过更多次了，那么什么都不用做。

● 在周期的最后1天

⏹ 按照前99天的规则做，然后：

◆ 如果灯泡关着，就打开（ON）。

◆ 如果已经是开着的了，则声称所以的人都来过灯泡房了。

这个协议的中心思想是这样的。总有一个周期里所有的人都会到达灯泡房，且只到达一次。即100天中每个人恰好都到达且只有一次到达灯泡房。这种理想情况下，灯泡的初始状态是开（ON），而因为每个人都只到达一次，所以没有人会动灯泡，灯泡维持着开状态（ON），而最后一个人到达并执行规则之后，灯泡依然开着（ON），那么，非常幸运的，他可以确定所有人都来过了。而如果在这100天中有一个人来灯泡房两次或两次以上（这意味着这100天中有其他什么别的人没有来灯泡房），那么这个灯泡就会被他关上，而灯泡一旦关上，除了最后一天，所有人都无权打开。最后一天，如果没有运气开到灯泡开着，罪犯就会重置灯泡状态，等待下一次机会。

期望时间

设X为此协议所需的天数，B为所需要度过的周期数，则一个周期足够幸运到让每个犯人恰好出去一次是一个几何分布，表达式为：

（n为囚犯数量）

几何分布的期望是概率的倒数，而X=nB，则

由斯特灵公式，（这个公式在时成立，我也不会证明，感兴趣的可以维基之），则

当n=100时，E[X]=1.072×1044天（这个数远远超过了一百亿年，而且比宇宙的年龄还要长），我觉得囚犯们宁可越狱也不会擎等着。所以，我们有必要设计一个更好的协议。

方法二、计数者

这个问题之所以很困难，可能就是大家不自觉的认为每个人都要照相同的规则行事，仔细思考之下，就会发现，其实没有这个限制。于是，就有了另外一个方法，我们挑出来一个人，称之为“计数者”。计数者的脑子里持有一个变量，我们称为T，T的初始值为1。每个犯人行事遵循以下准则：

● 不是计数者

⏹ 如果灯泡是着的，你之前从来没有打开过，就打开（ON）。

⏹ 如果灯泡是开着的，什么都不要做。

● 是计数者

⏹ 如果灯泡关着，什么都不做。

⏹ 如果灯泡是开着的，关掉（OFF），并且让T=T+1。

⏹ 如果T=n，声称所有的囚犯都已经来过了。

这个协议的中心思想是每个人都有一次机会将灯打开，并且只会打开一次。一旦灯被打开，没人能将灯泡关掉，只有计数者可以。每个人（除计数者）通过开灯表示自己来过了。灯一旦打开，别人就不能关闭，只能等待计数者关闭。计数者关到第99次的时候，他就可以确定100个人都来过了。

期望时间

这个有点难分析哈。让我们把时间拆分来分析。让Xi代表T=i的第一天和T=i+1第一天之间的天数，在这些天中，有两件事情会发生：

1、一个从未开过灯的囚犯被选中到灯泡房中游览，导致灯泡被打开（ON）。让Yi代表从T=i到此事件发生的天数。

2、计数者到来，将灯关上（OFF）。让Zi代表从灯泡被打开（ON）到计数者到来那一天之间的时间。

于是

设随机变量X为所需的总天数，则

细心的同学可能会发现，上面所有的分析对新囚犯到来的那一天属于Xi还是Yi语焉不详。但这不是一个问题，只要我们并没有漏掉一天活着多算一天。

Yi是一个几何随机变量，其参数是，Zi也是几何随机变量，参数是。于是

在大O中，，故

当n=100时，E[X]约为10417.74天，即28.54年，还在一个可接受范围内。年轻的犯人那时候都活着呢。到这里，终于满足了我的好奇心，我最初不过是想知道期望怎么计算。

当然，还可以计算方差神马的，大家可以到原网站上去看。

这个方法是“标准”解法，当然，还有一些不那么出名的协议，但性能更好，感兴趣的可以去看看。

本文来源：https://www.2haoxitong.net/k/doc/49102f2558fb770bf78a5565.html