Intersection of Lines

Date: 06/28/98 at 05:46:40
From: Andrew C.
Subject: Intersection of lines

Hi. This question has been puzzling me for a couple of days now and I 
was wondering if you could help me out. Thanks.

n co-planar lines are such that the number of intersection points is a 
maximum.

 (i) How many intersection points are there?

(ii) If n such lines divide the plane into Un regions; show that
     Un = U(n-1) + n. Hence deduce that Un = 1 + 1/2n(n+1)
     How many of these regions have finite area?

     Un is "U subscript n" and "U(n-1) is U subscript n minus 1"

Thanking you in advance,
Andrew

Date: 06/28/98 at 11:40:04
From: Doctor Anthony
Subject: Re: Intersection of lines

>(i) How many intersection points are there?

Two lines cut in 1 point. A third line will cut the other two lines 
in 2 more points, giving 1 + 2 = 3 points.

A fourth line will cut the other 3 lines in 3 more points, giving 
3 + 3 = 6 points.

So the series goes  n = 1,  2,  3,   4,   5,    6,  .......
Number of points        0,  1,  3,   6,  10,   15,  .......

The gap increases by 1 each time.  This is the sequence of triangular 
numbers which has the nth term given by n(n-1)/2.

If you made up a difference table, the second differences would be 
constant, so the nth term is a quadratic in n.

If you assume  f(n) = an^2 + bn + c,  where f(n) is the nth term

   n = 1    a +  b  + c =  0
   n = 2   4a + 2b  + c =  1
   n = 3   9a + 3b  + c =  3  and solving these 3 equations for a,b,c

a = 1/2, b = -1/2, c = 0  so f(n) = n^2/2 - n/2 = n(n-1)/2  
as given above.

So with n lines there are  n(n-1)/2 intersection points.

>(ii) If n such lines divide the plane into Un regions; show that
>     Un = U(n-1) + n. Hence deduce that Un = 1 + 1/2n(n+1)
>     How many of these regions have finite area?

With n = 1 we divide the plane into 2 regions. With n = 2 we have 4 
regions, with n = 3 we get 7 regions. A fourth line will meet the 
other 3 lines in 3 points and so traverses 4 regions, dividing them 
into two parts and adding 4 new regions. In general the nth line will 
add n new regions.

 u(1) = 2
 u(2) = 4
 u(3) = 7
 u(4) = 11  and so on, where u(n) = number of regions with n lines.

We get the recurrence relationship  

     u(n+1) = u(n) + (n+1)

We get the following chain of equations

     u(n) - u(n-1) =  n
   u(n-1) - u(n-2) =  n-1
   u(n-2) - u(n-3) =  n-2
  ........................
  ........................
     u(4) - u(3)   =   4
     u(3) - u(2)   =   3 
     u(2) - u(1)   =   2
  --------------------------
Add  u(n) - u(1)  =   2 + 3 + 4 + ..... + (n-1) + n


all other terms on the left cancel between rows.

     u(n) = u(1) + 2 + 3 + 4 + ....+ n   and u(1) = 2

     u(n) = 1 + [1+2+3+4+...+n]

          = 1 + n(n+1)/2

          = (2 + n^2 + n)/2

So   u(n) = (n^2+n+2)/2

The number of 'open' regions with 2 lines is 4, with three lines it is 
6, with 4 lines it is 8 and so on. With n lines the number of open 
regions is 2n. So the number of finite regions is given by:

       1 + n(n+1)/2 - 2n

- Doctor Anthony, The Math Forum
  http://mathforum.org/dr.math/