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.www.ddhw.com
哈哈哈哈 O(∩_∩)O哈哈~ 好久不来了，不小心看了一眼自己主页，发现自动关联了自己以往发过的帖，点进这个看了一眼，笑个半死。。。敢情我当初还发过这么搞笑的东西啊，我自己完全不记得了 
雷达卡
发表于 2006-2-16 21:41:46
收藏
分享
支持
反对
置顶卡
千斤顶
楼主