2006年美國高中生數學競賽最難題目

請問你有答案嗎?

我們稱可以達到題目要求的情況為＂完全連線＂，反之稱為＂不完全連線＂。

５個電腦以５個點ＡＢＣＤＥ表示
５個電腦的連線情形可以用５邊形＋對角線表示
∴可以有１０條連線
∵每條線有連線未連線之分
　　　10
∴有２　＝１０２４種可能的情況
每個情況出現機率相同
把所有的情況分為有０、１、２、３、４、５、６、７、８、９、１０個連線的圖形

∵任一部電腦要得到其他４部電腦的資料，至少必須有４條連線
∴有０、１、２、３連線的圖形是＂不完全連線＂。

∵如果光４台電腦連線，最多是６條連線
也就是說　有７、８、９、１０條連線的情形
必定可以得到第５部電腦的資料。這些情況都算＂完全連線＂。

剩下來的就是計算圖形中有４、５、６條連線中＂不完全連線＂的情形

（１）６條連線的情況中，＂不完全連線＂的情形，總共有５種，圖形例子是４邊形ＡＢＣＤ＋對角線２條。

也就是說，只在５邊形的圖形中數數看頂點在ＡＢＣＤＥ的的４邊形個數即可。

（２）５條連線的情況中，＂不完全連線＂的情形，總共有３０種，圖形例子是＂４邊形＋對角線＂少一個邊。
所以有５╳C(6,1)＝３０種

（３）４條連線的情況中，＂不完全連線＂的情形比較複雜，有兩種狀況：
第１種例子是＂４邊形＋對角線＂少２個邊。

共有５╳C(6,2)＝７５
第２種例子是三角形ＡＢＣ＋ＤＥ。也就是說，只在５邊形的圖形中數數看頂點在ＡＢＣＤＥ的的３角形個數即可。

故共有C(5,3)=10種

所以＂不完全連線＂的狀況總共有
０１　　２　　　３　　　４　　５　６
1+10+C(10,2)+C(10,3)+(75+10)+30+5 =296
=1+10+45+120+85+30+5
故可以＂完全連線＂的機率是
(1024-296)/1024=91/128

　假設任兩台完全連線，則需連接10條線，欲符合條件至少要四條線
1.10條線全部接上情形只有一種
1.若任意拆掉任一條線，二條線，三條線，皆可符合條件
共10+10*9/2+10*9*8/(3*2*1)=175
2.若任意拆掉四條線，需扣除其中四條線皆連至同一電腦的情形
10*9*8*7/(4*3*2*1)-5=205
3.若任意拆掉五條線，需扣除其中四條線皆連至同一電腦的情形
10*9*8*7*6/(5*4*3*2*1)-5*6=222
4.若任意拆掉六條線，需扣除(1)其中四條線皆連至同一電腦的情形(2)任選相鄰兩台電腦維持連線，但各拆掉另外三條線
　10*9*8*7/(4*3*2*1)-5*(6*5/2)-(5*4/2)=125

因此共有1+175+205+222+125=728，每一種情形依丟銅板的方式決定，機率為1/2^10

故欲接通五台電腦的機率為728/1024