问题的提出

\(n\) 个人, 每人有一个独家八卦消息. 任意人都可以打电话给别人, 交换双方目前已知的所有消息. 要想所有人都知道所有 \(n\) 条消息, 最少需要通多少次电话?

这个冠名为 gossip problem 的问题在不少的书上都有, 甚至小学的奥数, 但都不会有答案, 仿佛是一个很简单的问题. 其实不然! 单墫在数学竞赛研究教程 有一个习题, 采用数学归纳法证明了在 \(n\geqslant4\) 时, \(2n-4\) 次电话可以解决问题. 但这是平凡的, 不是困难所在.

这个问题还有另一个版本: 假设这 \(n\) 个人的联系方式不是打电话, 而是发邮件. 也就是说, 每个人都可以发邮件给随便挑选的他人, 把自己掌握的消息告知对方, 但对方了解的秘密不会泄漏. 那么, 要想每个人都知道所有 \(n\) 条消息, 最少需要发多少封邮件?

一些交待

我真正思考这个问题, 应该是06年的10-11月的一个晚上在北大南门街对面的上海城隍庙(已经消失2-3年), 遇上数学院一个朋友. 他在给学生讲奥数, 把这个题目发邮件的版本拿来问我. 在此之前是否看到过这问题, 不清楚, 但之后在奥数之家论坛有人问这个. 我在奥数之家回帖说明思路, 但没写详细证明. matrix67的博客引起我的注意后, 翻了一遍, 发现里面有打电话这种情况的一个证明, 并且交待此问题名 gossip problem. 我开始 Google, 于是回忆往事, 有了这个文章.

写这个文章的目的, 是谈论一个叫做 Label-connected graph 的事物, 这是我自己引进的第一个数学概念. 尽管在数学历史上, 已经有人在先, 但我是独立完成的. 当然, 也会交待清楚我以Label-connected graph为工具给出的解法, 以及收集到的别人的解答.

Brenda Baker 和 Robert Shostak 1972年的证明

这个证明转自matrix67.

显然, \(n=2\) 时只需要\(1\) 通电话, \(n=3\) 时必须要\(3\) 通电话. \(n=4\) 时, 可以让AB互相通话, CD互相通话, 此时每个人都知道了(包括自己的)两条消息;然后A和C通话, B和D通话, 从而使得每个人都获知另外两条自己还不知道的消息. 显然, 对于\(4\)个人的情况, \(4\)通电话已经是最少的了.
\(n>4\)的情况, 有一种算法可以保证在\(2n-4\)通电话内解决问题. 首先, 选出\(4\)个人作为消息汇总人. 其余每个人都选择一个汇总人并与之通话; 然后\(4\)个汇总人再用\(4\)通电话互相更新一下消息(用\(n=4\)的办法); 最后\(4\)个汇总人把电话再打回去, 实现所有消息全部共享.

下面我们证明, \(2n-4\) 已经是最少的了. 证明方法很多, 也都很复杂. 最常见的证明由Brenda Baker和Robert Shostak在1972年给出.

证明的关键在于这个引理: 如果我们可以在\(2n-5\)次电话以内达到要求, 则整个过程中绝对不会有人在电话中听到对方八卦自己的消息. 我们将用反证法来证明这一点. 首先找出最小的\(n\)使得\(n\)个人可以在\(2n-5\)次通话中传遍消息. 如果某个人\(G\) 听到了自己的消息, 表明整个过程中存在这么一条通话线路: \((G- G_1)(G_1-G_2)\dotsm(G_r-G)\). 现在, 我们把\(G\) 这个人去掉, 再重新安排一些通话线路, 使得剩下的\(n-1\)个人同样能在\(2(n-1)-5\) 次通话后传遍信息, 从而与\(n\)的最小性矛盾. 直接忽略上述”通话环”中的\((G – G_1)\)和\( (G_r-G )\)两条边.对于其他某个人\(P\)和\(G\)之间的通话\((P-G)\), 找出\((P-G)\)通电后最先出现的”通话环”中的其中一链(比如\((G_i-G_{i+1})\)). 在新方案中, 让 \(P\) 把电话打给\(G_i\). 这样, 原方案中任何一条由 \(P_1\) 带给 \(G\) 再带给\(P_2\) 的消息, 都由对应的 \(G_i\), \(G_j\) 以及他们之间的链条来完成, 即\((P_1-P_i)(G_i-G_{i+1})\dotsm(G_j-P_2)\). 新方案与原方案一样满足要求, 且通话次数减少了两次, 同样小于等于\(2n-5\).

每个人都不会听到自己的消息, 这可以推出一个很有趣的东西: 记一通电话的双方为A和B, 则要么A和B都还没打完, 要么这通电话对双方来说都是最后一通.原因很简单, 假如这通电话是A的最后一电, 这表明A和B都知道了所有的消息, 但B还要给别人打电话, 别人就会听到自己的消息. 类似地, 一通电话的双方要么都是第一次打, 要么都不是第一次打: 假如A的第一通电话是跟B打的, 但B之前已经和C通过话了, 那A的消息将永远与C的消息一起传递, 因此最终C听到A的消息时也会听到她自己的.

于是, 对于所有电话次数不超过\(2n-5\)的情况, \(n\)只能是偶数. 并且情况只可能是这样: 先两两配对拨打\(\frac n2\)通”处女电”, 然后中间打很多” 中介电话”, 最后再两个两个地打\(\frac n2\)个”最后一电”. 由于所有的”处女电”和”最后一电”加起来恰好有\(n\)通, 那么”中介电话”最多只能有\(n-5\)通. 又由于连通所有\(n\)个点至少要\(n-1\)条边, 可知这些”中介电话”构成了至少\(5\)个连通分量. 对于任何一个人来说, 在任何“最后一电”拨打之前, 她的消息最多只能够在其中两个连通分量内传递(她所在的连通分量和她“处女电”的对象所在的连通分量); 类似地, 所有“处女电”都打完了后, 每个人都只能收到两个连通分量内的消息(她自己的和“最后一电”的对象的). 对于一个特定的人\(G\)来说, 除去她自己, “处女电”的对象和“最后一电”的对象所在的连通分量, 至少还有两个连通分量, 里面的所有“中介电话”对她没有任何意义: 这些“中介电话”既不会把她的消息传出去, 也不会把别人的消息带给她.

设与G不相干的电话通数为\(c(G)\).

反过来, 又有多少通电话与\(G\)有关呢? 让我们继续把目光停留到G身上. 要想把她的消息传给所有人, 至少需要\(n-1\) 通电话; 要想让所有消息都传到她那里, 同样也得要n-1通电话. 某些电话可以同时起到这两种作用, 但有一个前提条件: 这些电话必需是她亲自打的. 否则, 她自己的消息将“捆绑”进那些将会传给她的消息里, 从而与引理矛盾. 假设她自己打了 \(v(G)\) 通电话, 那么总共有\(2n-2-v(G)\) 通电话负责传出她的消息并把别人的消息传给她. 由\(2n-5 \geqslant 2n-2-v(G)+c(G)\) 可知 \(v(G)\geqslant3+c(G) \geqslant 3\). 既然每个人都打了至少\(3\)电话, 这表明每个人都打过”中介电话”, 直接推出每个连通分量都有至少一条边. 前面说了, \(c(G)\)包含了至少两个连通分量中的所有边, 因此\(c(G)\geqslant2\). 因此, \(v(G)\geqslant5\). 每个人都打了至少\(5\)次电话? 这当然是不可能的, 这将导致总的电话数目比 \(2n\)  还大了.