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

某个导师要和 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

如果你对这个问题有兴趣,你一定会喜欢:http://www.matrix67.com/blog/archives/5342

19 条评论

发表评论




Enter Captcha Here :