Still celebrating National IT Professionals Day with 3 months of free Premium Membership. Use Code ITDAY17

x
?
Solved

Maximum number of regions n lines can dissect a plane

Posted on 2008-06-19
4
Medium Priority
?
276 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 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:blu
blu 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

Important Lessons on Recovering from Petya

In their most recent webinar, Skyport Systems explores ways to isolate and protect critical databases to keep the core of your company safe from harm.

Question has a verified solution.

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

Have you ever thought of installing a power system that generates solar electricity to power your house? Some may say yes, while others may tell me no. But have you noticed that people around you are now considering installing such systems in their …
This article seeks to propel the full implementation of geothermal power plants in Mexico as a renewable energy source.
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.
Although Jacob Bernoulli (1654-1705) has been credited as the creator of "Binomial Distribution Table", Gottfried Leibniz (1646-1716) did his dissertation on the subject in 1666; Leibniz you may recall is the co-inventor of "Calculus" and beat Isaac…

721 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