趣题：寻找隐藏的公共秘密

刚刚看到一道智力题，颇有些意思，说来给大家听听。我把题意稍微改了一下，原题中的 XX 侠是一个（不太容易解释的） lynch mob 。

某座城市里发生了一起命案，已经确定凶手是 8 个嫌疑犯之一。经过很多可靠的调查，城南和城北的两名警探各自独立地把嫌疑犯的名单缩减到了两个人。现在，两名警探正在通电话，他们试图对比一下彼此的调查结果。如果他俩的嫌疑犯名单中正好只有一处重合，他们就能确定出凶手的身份了。但问题是，这座城市里有一个伸张正义、凌驾于法律之上的 XX 侠，他正在窃听两名警探的通话。如果他从中获知了凶手的身份，他将在警方实施拘捕之前先杀死凶手。

现在， XX 侠已经知道了那 8 个嫌疑犯是谁，但不知道两名警探各自都把目标锁定在了哪两个人上。这两名警探之前从未见过面，这通电话是他们俩第一次进行交流。他们俩能成功地确定凶手的身份，而又不让 XX 侠知道凶手是谁吗？

（当然，这里我们不允许使用那些基于数论的公钥加密体系，不然题目就没啥意思了）

显然，要想秘密地传递消息，他们事先必须得有一个只有他们俩才知道的秘密。这个问题有趣就有趣在，两名警探之间并不是没有公共的秘密——他们是有一个公共秘密的，而这个公共的秘密恰恰是他们此次通话的目的。让我们来看看下面这种方案是如何利用这个公共秘密的。

为了便于叙述，我们把 8 个嫌疑犯用数字 1 到 8 编号。从 8 个嫌疑犯中选出 2 个人有 28 种情况，我们把这 28 种情况列成下表：

(1,2)(1,3)(1,4)(1,5)(1,6)(1,7)(1,8)

(3,4)(2,4)(2,3)(2,6)(2,5)(2,8)(2,7)

(5,6)(5,7)(5,8)(3,7)(3,8)(3,5)(3,6)

(7,8)(6,8)(6,7)(4,8)(4,7)(4,6)(4,5)

注意这个表的特点：每一列恰好都既无重复又无遗漏地包含了所有 8 个嫌疑犯。假设警探 A 的嫌疑犯名单是 (1,2) ，他就这样告诉警探 B ：

我的嫌疑犯名单在第一列中。

如果 B 的嫌疑犯名单也在第一列中，他就立即知道两份名单是一模一样的。因此 B 可以说：

洗洗睡吧，我们俩的嫌疑犯名单是一样的。

但若 B 的嫌疑犯名单不在第一列，对比一下自己手中的名单，他就能知道 A 的名单可能是第一列的哪两个了。比方说，如果 B 的两个嫌疑犯是 (2,7) ，他就知道了 A 的名单只可能是 (1,2) 或者 (7,8) 。接下来， B 就跟 A 说：

我名单中的两个人或者都在 1、2、7、8 这一组里，或者都在 3、4、5、6 这一组里。

由于 A 的两个嫌疑犯是 (1,2) ，当 A 听了 B 的这句话后，立刻就意会了：其实 B 的那两个人是在前一组里面的。此时， A 、 B 之间就有了一个公共的秘密！有了这个公共的秘密， A 、 B 之间的秘密交流就容易多了。比如说， A 可以借助这个公共秘密，大胆地把自己手中的名单告诉 B ：

我的名单是这一组中的前两个人。

或者更明确地说：

我的名单是 (1,2) 或者 (3,4) 。

B 也能立即明白， A 指的是 (1,2) 。一对比 B 自己的名单，哦，原来凶手是 2 号。于是 B 就可以说：

凶手是你的名单中编号大的那一个。

或者干脆说：

凶手是 2 号或者 4 号。

由于 XX 侠不知道他们讨论的是前一组还是后一组， XX 侠就只能听天书了。

知道答案后我不由得拍案叫绝，随后便开始静下心来仔细思考，究竟为什么两名警探能进行秘密通信？用于交流的公共秘密究竟是从哪里来的？其实，这个隐藏的公共秘密来源于双方的一个共识：我们两人的名单有交集。换句话说，如果 A 手中的名单是 (1,2) ， A 就知道了 B 的名单一定是(1,2), (1,3), … , (1,8), (2,3), (2,4), … , (2,8) 等 13 种情况中的一个。同时， B 也知道他自己的名单是这 13 种情况中的一个（因为他知道自己的名单是什么），因此这个信息就成了两人之间的一个隐藏着的公共秘密。

类似的情况还发生在很多其它的场合。比方说，有 1、2、3、4、5 五张牌，随机发给 A 和 B 两个人，每个人发两张牌。显然，他们俩互相之间都不知道对方手中的牌。现在，有一群人在旁边围观， A 能否把自己手中的牌告诉 B ，而不让围观者知道？这是有可能的，因为 A 、 B 两人享有一个别人都不知道的信息：他们知道对方手中没有什么牌！举个例子来说， A 手中的牌是 (1,2) ，那么 A 就知道 B 手中既没有 1 又没有 2。当然， B 自己肯定也知道这一点，因此他们就有了一个别人不知道的秘密信息。

怎样利用这个公共秘密呢？不妨像前面那样，把五选二的 10 种情况列成下表，其中每一列的 4 个数都不相同：

(1,2)(1,3)(1,4)(1,5)(2,3)

(3,4)(2,5)(3,5)(2,4)(4,5)

现在， A 只需要说自己的两张牌在哪一列就可以了。如果 A 说自己的牌在第一列，但 B 手中的牌是 (3,5) ，那么 B 就立即知道 A 的牌是 (1,2) 了，因为 A 不可能有 3。

继续深入的研究还能得出一些更有意思的结果：在打牌时，你甚至有办法把自己手中的牌秘密地告诉你的队友！