Solved

Maximum number of regions n lines can dissect a plane

Posted on 2008-06-19
4
267 Views
Last Modified: 2010-04-21
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
Comment
Question by:InteractiveMind
  • 2
4 Comments
 
LVL 53

Assisted Solution

by:Infinity08
Infinity08 earned 350 total points
ID: 21821475
Your formula is correct :

        http://mathworld.wolfram.com/PlaneDivisionbyLines.html
0
 
LVL 53

Accepted Solution

by:
Infinity08 earned 350 total points
ID: 21821480
Here's a proof by induction :

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

(no complicated maths ;) )
0
 
LVL 22

Assisted Solution

by:blu
blu earned 150 total points
ID: 21821653
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
 
LVL 25

Author Closing Comment

by:InteractiveMind
ID: 31468733
Thanks
0

Featured Post

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
Quadratic Equation 5 66
Revenue table 8 88
Need a nodal sequencing tool 3 76
C/R - what does it mean in postal address 2 68
Introduction On a scale of 1 to 10, how would you rate our Product? Many of us have answered that question time and time again. But only a few of us have had the pleasure of receiving a stack of the filled out surveys and being asked to do somethi…
This article seeks to propel the full implementation of geothermal power plants in Mexico as a renewable energy source.
Learn how to create flexible layouts using relative units in CSS.  New relative units added in CSS3 include vw(viewports width), vh(viewports height), vmin(minimum of viewports height and width), and vmax (maximum of viewports height and width).
This is a video describing the growing solar energy use in Utah. This is a topic that greatly interests me and so I decided to produce a video about it.

910 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

19 Experts available now in Live!

Get 1:1 Help Now