您当前的位置:首页 > 学习 > 阅览室

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

时间:12-12来源:作者:点击数:

刚刚看到一道智力题,颇有些意思,说来给大家听听。我把题意稍微改了一下,原题中的 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。

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

方便获取更多学习、工作、生活信息请关注本站微信公众号城东书院 微信服务号城东书院 微信订阅号
推荐内容
相关内容
栏目更新
栏目热门