Question

假定n個人各恰好知道一個消息，而所有n個消息都不相同，每次“A”打電話給“B”，“A”都把所知道的一切告訴“B”，而“B”不告訴“A”什么消息．為了使各人都知道一切消息．求所有需要兩人之間通話的最少次數(shù)．證明你的答案是正確的．

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次話；然后將它們相加即可．

解答：解：需要兩人之間通話的最少次數(shù)=

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號消息．
 這個方案打電話次數(shù)一共是（

n

2

-1）+2+n-4=

3n

2

-3（次）．

點評：本題考查了排列與組合的問題．解答此題時，人們往往漏掉這3種通電話的方式中，有4次電話是重復(fù)的．