每日一题 | 拜占庭将军问题

昨日问题

每日一题 | 一百个囚犯与一百个抽屉问题

这道题来源于读者投稿，解法来源于知乎。

很显然，每个囚犯最多打开50个抽屉，抽中自己号码的概率是1/2。但是我们有100个囚犯，这100个囚犯都找到自己号码的概率就是2的一百次方分之一。咱们也不必要去计算这个值，显然是一个天文数字。

那么有没有更好的策略呢？

其实是有的，并且非常巧妙，巧妙到几乎很难想到。策略是对于囚犯i，他首先打开i号抽屉，如果i号抽屉当中就是i，显然他成功找到了。假设抽屉当中是号码j，那么他继续打开j号抽屉，重复上述过程，直到找到了号码i或者是用完了50次机会。

比如在这个例子当中，所有人都可以在用完机会之前找到自己的号码。

那么这种操作的原理是什么？

原理就是找环，我们把问题进行抽象和转化。首先我们把抽屉上的号码看成是起始点，把抽屉里的卡片号码看成是终点。这样我们就连出了一条有向边，比如1号抽屉里是7号卡片，我们就得到了一条从1指向7的边，一共有100个抽屉100张卡片，所以就有100个点和100条边。

再加上每个点的入度和出度都是1，那么根据图论中点和边的性质，我们可以确定，每一个点都在环当中。那么剩下的就很好办了，环是确定的，不确定的就是环的大小。

对于一个确定的点i来说，它所在的环长度可能是1也可能是100。只要大于50，我们就无法找到解了。

那么这个概率应该怎么算呢？

首先，可以确定的是如果存在长度大于50的环，这个环一定只有1个。我们假设它的长度是L，那么，这个环的构成情况一共有C(100, L)种，这里的C表示组合数。对于每一种组合来说，一共有(L-1)!种排列，因为是一个环，所以不是L!。

这个环之外的元素有100-L个，它们的排列有(100 - L)!种。对于每一个L都有C(100, L) * (L-1)! * (100 - L)!=100!/L种情况。而100个数的总排列是100!，所以我们可以得到所有囚犯都猜对的概率是：

这里的计算看起来复杂，其实用到的只是小学的奥数排列组合的知识。不管怎么说，从结果上来看，这个概率显然比瞎猜要大得多的多了。

今日问题

拜占庭将军问题

拜占庭帝国为了征讨一座城堡派出了7个将军各自率领一个队伍，这个城堡非常坚固，必须要有一半以上的将军一起进攻才可以获胜，否则将会失败。由于科技落后，将军之间只能通过传令兵进行通信。

将军之间约定各自发出是否进攻的投票，如果收到进攻的意见超过半数则发起进攻。但由于7个将军当中混入了2个叛徒，叛徒会发出虚假的指令，比如向决定进攻的将军发送进攻，向想要撤退的将军发出撤退。比如3个忠诚的将军下令进攻，2个将军下令撤退，这时两个叛徒向3个忠诚的将军发送进攻，向2个想要撤回的将军发送撤退，这样将会导致实际进攻的将军只有3个，这会导致战争的失败。

假设现在将军们已经发现了叛徒的存在但不知道是哪两个将军是叛徒，忠诚的将军们应该采用什么样的方法才可以保证做出的决策不被叛徒影响？