Associated Topics || Dr. Math Home || Search Dr. Math

### 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"

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

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/
```
Associated Topics:
High School Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search