Solved

Maximum number of regions n lines can dissect a plane

Posted on 2008-06-19
4
268 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

Enterprise Mobility and BYOD For Dummies

Like “For Dummies” books, you can read this in whatever order you choose and learn about mobility and BYOD; and how to put a competitive mobile infrastructure in place. Developed for SMBs and large enterprises alike, you will find helpful use cases, planning, and implementation.

Question has a verified solution.

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

Suggested Solutions

Title # Comments Views Activity
Whisker Plot 1 43
Word Problem 4 83
Math question 3 87
How to install SVN Command Line Client? 5 66
This article provides a brief introduction to tissue engineering, the process by which organs can be grown artificially. It covers the problems with organ transplants, the tissue engineering process, and the current successes and problems of the tec…
When we purchase storage, we typically are advertised storage of 500GB, 1TB, 2TB and so on. However, when you actually install it into your computer, your 500GB HDD will actually show up as 465GB. Why? It has to do with the way people and computers…
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…

773 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