通信复杂度问题：利用特殊机器判断公共元素的存在性

某个导师要和 A 、 B 两名学生玩一个游戏。导师会把 A 、 B 两名学生分别放进两间小黑屋里，每间屋子里都有一台电脑，这两台电脑之间只有一条通信线路。然后，导师会想一个正整数 n （可能会非常非常大），把它的值告诉这两名学生；再构造出集合 {1, 2, …, n} 的两个子集，分别交给这两名学生。于是，每个人都知道了 n 的值和 {1, 2, …, n} 的一个子集。两人需要合作确定出，他们手中的集合是否包含公共的元素。他们之间交流信息的唯一途径就是那条通信线路，但他们能够使用的流量是有限的。具体能够使用多少 bit 的流量，这可以由他们自己决定，但必须在游戏开始之前（也就是 n 的值确定之前）就定好并告诉导师。

和其他类似的问题一样，在游戏开始之前，两人可以商量一个对策。不过，这一回，两人商量了很久，始终无法找到一个必胜的对策。就在两人快放弃的时候，他们突然发现，两人的通信线路上存在一个“漏洞”：两人都可以不计流量地访问一台特殊的第三方机器，我们不妨把它叫做机器 O 。不过，机器 O 只能做一件事情：从 A 那儿读取一个 1 到 n 的排列，从 B 那儿读取一个 1 到 n 的排列，然后计算出这两个排列复合之后是否恰好含有一个循环，并将计算结果分别告知 A 和 B 。然后，机器 O 就会自动关机，再也不能访问了。也就是说，A 和 B 只能使用机器 O 一次。注意， A 、 B 两人是无法看到对方传给机器 O 的数据的，另外机器 O 只能用于处理 1 到 n 之间的排列，不能处理其他大小的排列。

这里我们简单说明一下复合排列以及循环数量的意思。我们可以把一个排列想象成是 {1, 2, …, n} 到 {1, 2, …, n} 的一种映射关系， A 、 B 两个排列的复合，也就可以看作是每一个数经过 A 、 B 两次映射后的结果。举个例子，假如 n = 7 ， A 给机器 O 发送的是

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

B 给机器 O 发送的是

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

那么机器 O 就会计算这两个排列复合之后的结果：

(2, 3, 5, 1, 7, 6, 4) · (1, 4, 6, 2, 7, 3, 5) = (4, 6, 7, 1, 5, 3, 2)

如果在某个排列当中出现了 a 映射到 b 、 b 映射到 c 、 c 映射到 d 、 d 又映射到 a 一类的情况，我们就说这个排列里有一个循环。注意到 (4, 6, 7, 1, 5, 3, 2) 里面包含 3 个循环： 1 → 4 → 1 ， 2 → 6 → 3 → 7 → 2 ， 5 → 5 。因此，机器 O 将会给 A 、 B 两人各发送一条信息：“复合排列并非只含一个循环”。根据规则，紧接着，机器 O 将会立即关机，永久性地停止服务。

在这样的条件下， A 、 B 两人有必胜的策略吗？

A 和 B 有必胜策略。首先，让我们来看一个非常朴素的策略。每个人都按照下面的规则构造一个 1 到 n 的排列：先把自己集合里的所有数都放入正确的位置，再把其余数依次放进往右数第一个空位里（最右边的那个数则放进最左边的空位里）。比方说，当 n = 10 时，如果某个人手中的集合是 {3, 4, 7} ，那么他首先应该把 3, 4, 7 这三个数放进正确的位置里，得到 (_, _, 3, 4, _, _, 7, _, _, _) ，然后再把其他数循环向右挪动一位，于是得到 (10, 1, 3, 4, 2, 5, 7, 6, 8, 9) 。容易看出，如果 A 、 B 两人都这么做了的话，那么对由此得到的两个排列进行复合之后，每一个公共元素都会映射到自己，从而成为一个长度为 1 的循环。此时，机器 O 返回的必然是“含有多个循环”。

只可惜，这种策略没法保证，当两个集合没有公共元素时，复合排列一定只有一个循环。怎么办呢？没关系。下面我们来证明这样一个有用的结论：此时，如果两个人手中都没有的数正好有奇数个，那么复合排列一定只有一个循环！记住，下面这一大段文字有一个最基本的假设：假设两个集合没有公共元素。

我们用一种新的方法表示 A 和 B 提交的排列。首先，在左右两边都写下 1, 2, 3, …, n 这么一列数。如果 A 的排列中的第 i 个数是 j ，就从左边的 i 出发，画一个箭头指向右边的 j ；如果 B 的排列中的第 i 个数是 j ，就从右边的 i 出发，画一个箭头指向左边的 j 。于是，对于这 2n 个数里的每一个数来说，都有且仅有一个从它出发的箭头，也都有且只有一个指向它的箭头。为了考察 A 、 B 两个排列复合的结果，只需要看一看左边的每个数沿着箭头走到右边，再沿着箭头走回左边后，会到达哪个数即可。当 n = 10 时，如果 A 手中的集合是 {3, 4, 7} ， B 手中的集合是 {1, 10} ，那么整个图就如左图所示。如果 B 手中的集合不是 {1, 10} ，而是 {1, 9, 10} ，那么整个图就如右图所示。

现在，假设我们任意找一个数（不管是左边的还是右边的），从这个数出发，沿着箭头不断地走，最终结果会怎样呢？容易看出，我们永远不会走死（因为对于每个数来说，都有一条从这里出发的路），也不会突然走到一个刚才在半途中经过的数（因为对于每个数来说，都只有一条通向这里的路），因而最终一定会回到出发点。这说明，图中的任何一个数都在某个“圈”里。但是，根据 A 和 B 构造排列的策略，左边最多只有一个数会指向比自己大的数，右边也最多只有一个数会指向比自己大的数，而这种从小数指向大数的箭头是任何一个圈里必须具有的（除非是那种在两个相同的数之间来回一次形成的长度为 2 的圈，但由于 A 、 B 手中没有公共的数，因而这样的圈是不存在的）。因此，我们得出，整个图里最多只能有两个圈。接下来我们证明，如果两个人手中都没有的数有奇数个，那么整个图里必定只有一个圈。注意到以下三点：

1. 一个圈的长度总是偶数。这是因为，每个圈里的元素都是按照“左→右→左→右”的顺序交替的，因而这里面显然含有偶数个元素。
2. 如果数字 i 是 A 有 B 无或者 A 无 B 有的数，那么左边那个 i 和右边那个 i 一定都在同一个圈里。这是因为，如果 A 手中有数字 i ，这就意味着存在一根从左边那个 i 指向右边那个 i 的箭头；如果 B 手中有数字 i ，这就意味着存在一根从右边那个 i 指向左边那个 i 的箭头，不管怎样，这两个 i 都必定在同一个圈里。
3. 假设图中有两个圈。如果数字 i 是两个人手中都没有的数，那么图中的两个 i 一定分属两个不同的圈。这是因为，假设图中有两个圈，这就意味着每个圈里都只有一次从小数走向大数的机会，其余时候都是单向地从大数走到小数，没有回头的机会，要想同时包含这两个 i ，必须借助一个横向连接这两个 i 的箭头。然而，考虑到两个人手中都没有 i ，因此左右两个 i 之间没有任何箭头连接。可见，这两个 i 不可能属于同一个圈，只可能分别位于两个圈里。

我们几乎可以立即得出，假设图中有两个圈，那么两个人手中都没有的数一定有偶数个。根据第 2 点，那些一方持有的数总是两个两个地计入同一个圈里，因而每个圈里都已经有偶数个元素了。剩下的数则是两人手中都没有的数，根据第 3 点，每个数都会在两个圈里各出现一次。然而，根据第 1 点，每个圈里的总元素个数必须有偶数个，因而那些两人手中都没有的数一定有偶数个。

反过来，如果两个人手中都没有的数有奇数个，那么整个图中就只有一个圈了。有一个圈说明什么？这说明，从左边的任意一个元素出发，可以先按照 A 所构造的排列转移到右边的某个元素，再按照 B 所构造的排列回到左边的某个元素，不断这么做下去，便可遍历左边的所有元素。这就说明了，两个排列的复合结果一定只含一个循环。我们把这个结论再完整地叙述一下：若两人手中不存在公共元素，并且两人手中都没有的数有奇数个，那么按照之前讲过的方法构造排列，复合结果一定只含一个循环。

如果 A 和 B 能够合作推出，它们两人手上都没有的数到底是奇数个还是偶数个，问题就解决了。如果两人手中都没有的数有奇数个，两人可以直接使用上述策略，机器 O 回答“多个循环”，当且仅当两人手中有公共的元素。如果两人手中都没有的数有偶数个呢？两人就互相通告一下数字 1 在不在自己手中。如果两人手中都没有数字 1 ，那么 A 就修改自己的集合，把数字 1 添加进去；如果某个人手中有数字 1 ，另一个人手中没有数字 1 ，那么前者就把数字 1 从自己的集合中去掉。如此修改集合不会改变公共元素的存在性，但两人手中都没有的数就会变为奇数个，之前的策略就又可以使用了。当然，这里还有一种可能性：两个人手中都有数字 1 。此时，两人根本无需任何策略，直接宣布存在公共元素即可。

因此，我们最后的问题就是：两人如何合作推出他们手上都没有的数究竟有奇数个还是偶数个？这乍看上去非常困难，不过注意到，两人可以假设他们手上没有公共的元素，然而在这个假设下，刚才的任务是很容易完成的： A 和 B 可以互相通告一下自己手中有多少个数，然后用 n 减去 A 手中的元素个数，再减去 B 手中的元素个数，得到的就是两个人手中都没有的元素个数了。由于 n 的值有可能非常大，每个人手中的数都有可能很多很多，因此互相通告元素个数的时候究竟会花费多少流量，事先是没法预估出来的。不过没关系，两人只需要推出双方都没有的元素个数的奇偶性，因此两人只需要互相通告自己手中的元素个数的奇偶性即可。

因而，我们就得到了一个完整的必胜策略：

1. A 、 B 两人互相给对方发送一个 bit 的信息，告诉对方数字 1 在不在自己的集合当中。
2. 如果两人手中都有数字 1 ，则表明两人手中有公共元素，协议立即结束；否则，协议继续进行。
3. A 、 B 两人互相给对方发送一个 bit 的信息，告诉对方自己的手中有奇数个数还是偶数个数。
4. 如果刚才互发的两个 bit 相同并且 n 为偶数，或者刚才互发的两个 bit 不同并且 n 为奇数，则两人按照下述约定修改自己的集合：有数字 1 的人把数字 1 去掉，都没有的话 A 就把数字 1 给加进去。
5. A 、 B 两人按照之前说过的方法构造排列，然后发送给机器 O 。
6. 若机器 O 返回“存在多个循环”，则表明两人手中有公共元素；若机器 O 返回“只有一个循环”，则表明两人手中没有公共元素。

排除掉与机器 O 之间的通信，整个协议最多只会耗费 4 个 bit 的流量。换句话说， A 、 B 两人只需要向导师申请 4 个 bit 的流量就够了。

题目来源：http://www.brand.site.co.il/riddles/201010q.html