Question

两条直线上各有n个点,用这n对点按如下规则连结线段:

①同直线上的点不连结;

②连结的任意两条线段可以有共同的端点,但不得有其它的端点;

(1)画图说明当n=1、2、3时,连结的线段最多各有多少条?

(2)由(1)猜想n(n为正整数)对点之间连结的线段最多有多少条,证明你的结论.

(3)当n=2003时,所连结的线段最多有多少条?

Answer 1

(1)由图2可以看出,n=1时,最多可以连结1条线段,n=2时,最多可以连结3条线段,n=3时,最多可以连结5条线段.

(2)猜想:对于正整数n,这n对点之间连结的直线段最多有2n-1条.

证明: 将直线标记为l₁,l₂,它们上面的点从左到右排列为A₁,A₂A₃,┉,A_n和B₁,B₂,B₃,┉,B_n,设这n对点之间连结的直线段最多有P_n条,显然,其中必有A_nB_n这一条,否则,P_n就不是最多的数.

当在l₁,l₂分别加上笫n+1个点时,不妨设这两个点在A_n与B_n的右侧,那么除了原来已经有的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为端点的线段的条数大于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都已连结,此时图中的线段数为P_n+1,我们做如下操作:

去掉A_n+1B_i,连结A_nB_i+1,得到新的连结图,而新的连结图满足要求且线段总数不变,将此操作一直续断下去,直到与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(条).