Counting Regions Formed by Straight LinesDate: 04/18/98 at 15:00:29 From: Jay Shah Subject: Infinite divisions of a plane Dear Doctor Math - I have been exploring dividing planes into distinct regions with straight lines, mainly what happens when more lines are added. The way you add them seems to make a big difference in the number of regions you come up with. My question is: how many regions are formed by n straight lines if no three meet in a single point and no two are parallel? I have come up with .5n^2+.5n+1, which I think is the maximum number of regions possible. Now what happens if parallelism is allowed? What happens if concurrence is allowed? What happens if both are allowed? I would really appreciate it if you could see what you could come up with for this problem. I greatly appreciate any help you can give me. Thank you very much. From a great lover of math, Jay Shah Date: 04/18/98 at 15:29:33 From: Doctor Anthony Subject: Re: Infinite divisions of a plane Suppose we draw n straight lines on the plane so that every pair of lines intersects (but no 3 lines intersect at a common point). Into how many regions do these n lines divide the plane? 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 traverse 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 -------------------------- u(n) - u(1) = 2 + 3 + 4 + ..... + (n-1) + n which we find by summing the equations. All other terms on the left cancel between rows. We are left with: u(n) = u(1) + 2 + 3 + 4 + ....+ n and u(1) = 2 Thus: 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 If you allow parallel lines and more than 2 lines to intersect at a point, the answer becomes undefined. -Doctor Anthony, The Math Forum Check out our web site! http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/