流言问题

constant · 发表于 2006-2-16 21:41:46

难度：+++++

有N个家庭妇女，每人知道一条不同的流言（gossip）。然后她们开始互相打电话。每次电话有两个人参加，而且这两个人会交换她们知道的所有流言。她们至少要打多少次电话才能让所有人都知道所有N条流言？

huxlnn · 发表于 2006-2-17 05:04:35

n<=3 2N-3次

n>3 2N-4次

本贴由[huxlnn]最后编辑于：2006-2-19 1:31:30

constant · 发表于 2006-2-17 20:39:41

能证明吗？

yaluzangbu · 发表于 2006-2-18 07:17:48

For n = 2,3, F(n) = 2n-3; for n>=4, F(n) = 2n-4.
It is relatively easier to show F(n) <= 2n-4. Indeed, it can be shown to be true one by one for n=4,5,6,7. For n>=8, it can be proven by induction. For n=2k, the gossips are first shared among pairs, then k representatives (one for each pair) share info in 2k-4 steps, finally all info are passed to other k representatives -- altogether 4k-4 steps. The case of odd numbers, though more tricky, can be treated similarly.

It is more tough to prove F(n) >= 2n-4. In fact I haven't succeeded. It's really a nice problem. Constant, where did you get all these wonderful problems? Thank you for making this place so attractive.

constant · 发表于 2006-2-19 03:34:23

另一半非常难。我看看有没有时间把我知道的证明写得好懂一点贴出来。

huxlnn · 发表于 2006-2-19 07:41:54

当n=2,3时,容易知通话次数分别为1,和3,

当n>3时,取第1,2两人作为A列,另外n-2人在B列,则

一、B列依次向后积累信息,当第n-1人向第n人完成通话后,此两人知道B列全部信息,共通话n-3次;

二、A列中两人通话一次,都知道了A列的全部信息,通话1次;

三、B列第n人向A列第2人通话，第n-1人向A列第1人通话;通话结果此4人都知道了全部信息，共通话2次

四、B列第n人向B列除第n-1人外的n-4人传递所知全部信息，通话n-4次，全部人员知道全部信息，

故总的通话次数为n-3+1+2+n-4=2n-4次

寒潭清 · 发表于 2006-2-20 15:33:42

		自动登录	找回密码
密码			立即注册

动态微博

流言问题

回复：流言问题

能证明吗？

回复：流言问题

这一半对

参考楼上的意见,给出过程如下:

[@};-][@};-][@};-][@};-]