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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.