Question

兩條直線上各有n個點,用這n對點按如下規(guī)則連結線段:

①同直線上的點不連結;

②連結的任意兩條線段可以有共同的端點,但不得有其它的端點;

(1)畫圖說明當n=1、2、3時,連結的線段最多各有多少條?

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

(3)當n=2003時,所連結的線段最多有多少條?

Answer 1

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

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

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

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

所以P_n+1≥P_n+2.

另一方面,設對于n+1對點有另一種連法:

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

去掉A_n+1B_i,連結A_nB_i+1,得到新的連結圖,而新的連結圖滿足要求且線段總數(shù)不變,將此操作一直續(xù)斷下去,直到與A_n+1連結的線段只有一條A_n+1B_n+1為止.最后圖中,與點B_n+1相關的線段 只剩兩條,即A_nB_n+1,A_n+1B_n+1,去掉這兩條線段,則剩余P_n+2-2條線段,而圖形恰是n對點的連結 圖,所以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)當n=2003時,P₂₀₀₃=4005(條).