Question

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

Answer 1

分析：分三種情況：（1）2～

n

2

號(hào)每人給1號(hào)打1次電話；（2）1號(hào)和

n+1

2

號(hào)通1次電話，

n

2

號(hào)和n號(hào)通1次電話；（3）2～

n

2

-1號(hào)，

n+1

2

～n-1號(hào)，每人與1號(hào)（或者

n

2

，

n+1

2

，n號(hào)中的任意1人）通1次話；然后將它們相加即可．

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

3n

2

-3（次）．
給n個(gè)人分別編號(hào)1～n，他們知道的消息也編上相同的號(hào)碼．
（1）2～

n

2

號(hào)每人給1號(hào)打1次電話，共

n

2

-1次，1，

n

2

號(hào)得到1--

n

2

號(hào)消息．
（2）1號(hào)和

n+1

2

號(hào)通1次電話，

n

2

號(hào)和n號(hào)通1次電話，這時(shí)1，

n

2

，

n+1

2

，n號(hào)這4個(gè)人都知道了1-n號(hào)消息．
（3）2～

n

2

-1號(hào)，

n+1

2

～n-1號(hào)，每人與1號(hào)（或者

n

2

，

n+1

2

，n號(hào)中的任意1人）通1次話，這n-4人也全知道了1～n號(hào)消息．
 這個(gè)方案打電話次數(shù)一共是（

n

2

-1）+2+n-4=

3n

2

-3（次）．

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