我真正思考这个问题 应该是06年的10-11月的一个晚上在北大南门街对面的上海城隍庙(已经消失2-3年) 遇上数学院一个朋友. 他在给学生讲奥数 把这个题目发邮件的版本拿来问我. 在此之前是否看到过这问题 不清楚 但之后在奥数之家论坛有人问这个. 我在奥数之家回帖说明思路 但没写详细证明. matrix67的博客引起我的注意后 翻了一遍 发现里面有打电话这种情况的一个证明 并且交待此问题名 gossip problem. 我开始 Google 于是回忆往事 有了这个文章.
写这个文章的目的 是谈论一个叫做 Label-connected graph 的事物 这是我自己引进的第一个数学概念. 尽管在数学历史上 已经有人在先 但我是独立完成的. 当然 也会交待清楚我以Label-connected graph为工具给出的解法 以及收集到的别人的解答.
下面我们证明 \(2n-4\) 已经是最少的了. 证明方法很多 也都很复杂. 最常见的证明由Brenda Baker和Robert Shostak在1972年给出.
每个人都不会听到自己的消息 这可以推出一个很有趣的东西: 记一通电话的双方为A和B 则要么A和B都还没打完 要么这通电话对双方来说都是最后一通.原因很简单 假如这通电话是A的最后一电 这表明A和B都知道了所有的消息 但B还要给别人打电话 别人就会听到自己的消息. 类似地 一通电话的双方要么都是第一次打 要么都不是第一次打: 假如A的第一通电话是跟B打的 但B之前已经和C通过话了 那A的消息将永远与C的消息一起传递 因此最终C听到A的消息时也会听到她自己的.