Label-connected graphs and the gossip problem
问题的提出 \(n\) 个人, 每人有一个独家八卦消息. 任意人都可以打电话给别人, 交换双方目前已知的所有消息. 要想所有人都知道所有 \(n\) 条消息, 最少需要通多少次电话? 这个冠名为 gossip problem 的问题在不少的书上都有, 甚至小学的奥数, 但都不会有答案, 仿佛是一个很简单的问题. 其实不然! 单墫在数学竞赛研究教程 有一个习题, 采用数学归纳法证明了在 \(n\geqslant4\) 时, \(2n-4\) 次电话可以解决问题. 但这是平凡的, 不是困难所在. 这个问题还有另一个版本: 假设这 \(n\) 个人的联系方式不是打电话, 而是发邮件. 也就是说, 每个人都可以发邮件给随便挑选的他人, …
Label-connected graphs and the gossip problem Read More