[Webinar] Streamline your web hosting managementRegister Today

x
?
Solved

Maximum number of regions n lines can dissect a plane

Posted on 2008-06-19
4
Medium Priority
?
282 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 1400 total points
ID: 21821475
Your formula is correct :

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

Accepted Solution

by:
Infinity08 earned 1400 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:Brian Utterback
Brian Utterback earned 600 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

Learn to develop an Android App

Want to increase your earning potential in 2018? Pad your resume with app building experience. Learn how with this hands-on course.

Question has a verified solution.

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

Foreword (May 2015) This web page has appeared at Google.  It's definitely worth considering! https://www.google.com/about/careers/students/guide-to-technical-development.html How to Know You are Making a Difference at EE In August, 2013, one …
We are taking giant steps in technological advances in the field of wireless telephony. At just 10 years since the advent of smartphones, it is crucial to examine the benefits and disadvantages that have been report to us.
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.
Finds all prime numbers in a range requested and places them in a public primes() array. I've demostrated a template size of 30 (2 * 3 * 5) but larger templates can be built such 210  (2 * 3 * 5 * 7) or 2310  (2 * 3 * 5 * 7 * 11). The larger templa…

607 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