Question

假定n个人各恰好知道一个消息，而所有n个消息都不相同，每次“A”打电话给“B”，“A”都把所知道的一切告诉“B”，而“B”不告诉“A”什么消息．为了使各人都知道一切消息．求所有需要两人之间通话的最少次数．证明你的答案是正确的．

Answer 1

分析：分三种情况：（1）2～

n

2

号每人给1号打1次电话；（2）1号和

n+1

2

号通1次电话，

n

2

号和n号通1次电话；（3）2～

n

2

-1号，

n+1

2

～n-1号，每人与1号（或者

n

2

，

n+1

2

，n号中的任意1人）通1次话；然后将它们相加即可．

解答：解：需要两人之间通话的最少次数=

3n

2

-3（次）．
给n个人分别编号1～n，他们知道的消息也编上相同的号码．
（1）2～

n

2

号每人给1号打1次电话，共

n

2

-1次，1，

n

2

号得到1--

n

2

号消息．
（2）1号和

n+1

2

号通1次电话，

n

2

号和n号通1次电话，这时1，

n

2

，

n+1

2

，n号这4个人都知道了1-n号消息．
（3）2～

n

2

-1号，

n+1

2

～n-1号，每人与1号（或者

n

2

，

n+1

2

，n号中的任意1人）通1次话，这n-4人也全知道了1～n号消息．
 这个方案打电话次数一共是（

n

2

-1）+2+n-4=

3n

2

-3（次）．

点评：本题考查了排列与组合的问题．解答此题时，人们往往漏掉这3种通电话的方式中，有4次电话是重复的．