Question

兩條直線上各有n個(gè)點(diǎn),用這n對(duì)點(diǎn)按如下規(guī)則連結(jié)線段:

①同直線上的點(diǎn)不連結(jié);

②連結(jié)的任意兩條線段可以有共同的端點(diǎn),但不得有其它的端點(diǎn);

(1)畫圖說(shuō)明當(dāng)n=1、2、3時(shí),連結(jié)的線段最多各有多少條?

(2)由(1)猜想n(n為正整數(shù))對(duì)點(diǎn)之間連結(jié)的線段最多有多少條,證明你的結(jié)論.

(3)當(dāng)n=2003時(shí),所連結(jié)的線段最多有多少條?

Answer 1

(1)由圖2可以看出,n=1時(shí),最多可以連結(jié)1條線段,n=2時(shí),最多可以連結(jié)3條線段,n=3時(shí),最多可以連結(jié)5條線段.

(2)猜想:對(duì)于正整數(shù)n,這n對(duì)點(diǎn)之間連結(jié)的直線段最多有2n-1條.

證明: 將直線標(biāo)記為l₁,l₂,它們上面的點(diǎn)從左到右排列為A₁,A₂A₃,┉,A_n和B₁,B₂,B₃,┉,B_n,設(shè)這n對(duì)點(diǎn)之間連結(jié)的直線段最多有P_n條,顯然,其中必有A_nB_n這一條,否則,P_n就不是最多的數(shù).

當(dāng)在l₁,l₂分別加上笫n+1個(gè)點(diǎn)時(shí),不妨設(shè)這兩個(gè)點(diǎn)在A_n與B_n的右側(cè),那么除了原來(lái)已經(jīng)有的P_n條直線段外,還可以連結(jié)A_n+1B_n,A_n+1B_n+1這兩條線段,或連結(jié)A_nB_n+1,A_n+1B_n+1,這兩條線段.

所以P_n+1≥P_n+2.

另一方面,設(shè)對(duì)于n+1對(duì)點(diǎn)有另一種連法:

考慮圖3中以A_n+1為端點(diǎn)的線段,若以A_n+1為端點(diǎn)的線段的條數(shù)大于1,則一定可以找到一個(gè)i≤n,使得對(duì)于任意的j<i,A_n+1B_j都不在所畫的線段中,這時(shí),B_i+1,B_i+2,┉,B_n+1只能與A_n+1連結(jié),不妨設(shè)A_n+1B_i+1,A_n+1B_i+2,┉,A_n+1B_n+1都已連結(jié),此時(shí)圖中的線段數(shù)為P_n+1,我們做如下操作:

去掉A_n+1B_i,連結(jié)A_nB_i+1,得到新的連結(jié)圖,而新的連結(jié)圖滿足要求且線段總數(shù)不變,將此操作一直續(xù)斷下去,直到與A_n+1連結(jié)的線段只有一條A_n+1B_n+1為止.最后圖中,與點(diǎn)B_n+1相關(guān)的線段 只剩兩條,即A_nB_n+1,A_n+1B_n+1,去掉這兩條線段,則剩余P_n+2-2條線段,而圖形恰是n對(duì)點(diǎn)的連結(jié) 圖,所以P_n+1-2≤P_n.

由此,我們得到P_n+1=P_n+2,而P₁=1,P₂=3,所以P_n=1+2×(n-1)=2n-1.

(3)當(dāng)n=2003時(shí),P₂₀₀₃=4005(條).