Improve company productivity with a Business Account.Sign Up

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 283
  • Last Modified:

Maximum number of regions n lines can dissect a plane

I want to find the maximum number of regions that n lines can dissect a plane into.
Let F(n) represent this number.

Through trial and error, I have found that:

F(0)=1
F(1)=2
F(2)=4
F(3)=7

From which I have found a pattern:

F(n) = n + F(n-1)  =>  F(n) = n(n+1)/2 + 1 .

This equation makes some sense, but (assuming that it's accurate for all n), how would I PROVE it to be true?
As all I've done so far, is throw some extrapolation on top of some trial-and-error. Hardly rigorous.

Is such a proof something which I'd be capable of 'getting'? Or, does it depend on some very high-level mathematics?

Thanks
0
InteractiveMind
Asked:
InteractiveMind
  • 2
3 Solutions
 
Infinity08Commented:
Your formula is correct :

        http://mathworld.wolfram.com/PlaneDivisionbyLines.html
0
 
Infinity08Commented:
Here's a proof by induction :

        http://www.jimloy.com/geometry/plane.htm

(no complicated maths ;) )
0
 
Brian UtterbackPrinciple Software EngineerCommented:
You can always add a line that intersects all of the previous lines and does not pass through any previous point of intersection. Any line that is not parallel to any of the existing lines will pass through all of them. Thus, when adding the N+1 line, it will intersect with all of the previous N lines at exactly N points. Each of these N points is the endpoint of a line segment that bisects an existing region. If we consider the two regions bisected by the line after it no longer intersects any other lines, then as we follow the new line, each of the N intersection points adds one new region, plus the region left over when there is no more intersection points. Thus, for an existing plane with N lines, forming R(N) regions, adding one more line produces N+1 lines with R(N+!) regions, where R(N+1) = R(N) + N + 1. If we change that to a form in N, we get R(N) = N + F(N-1), which is what you had.

Is that sufficient? The conversion of the recurrence relation into a closed form just follows normal methods.
0
 
InteractiveMindAuthor Commented:
Thanks
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

Join & Write a Comment

Featured Post

Free Tool: ZipGrep

ZipGrep is a utility that can list and search zip (.war, .ear, .jar, etc) archives for text patterns, without the need to extract the archive's contents.

One of a set of tools we're offering as a way to say thank you for being a part of the community.

  • 2
Tackle projects and never again get stuck behind a technical roadblock.
Join Now