Problem 8. (The Plane Problem)

There are two parts to this problem. The first part is not awfully difficult but if you can solve the second part, you are very smart indeed! We don't really expect anyone to get the answer, but if anyone does, we would really like to know this person.

1. What is the maximum number of parts you can subdivide the plane by n lines, for n = 1, 2, 3, 4, and 5 lines ?

2. What is the general formula for the maximum number of parts you can subdivide a plane by n lines ?

Solution

We start by drawing one line that divides the plane into 2 parts. We then draw a second line not parallel to the first line which will then subdivide the plane into 4 parts as shown below.

It is clear the second line should not be parallel to the first line or else it would subdivide the plane into only 2 or 3 parts, depending on whether the lines were identical or distinct. It should also be clear that all additional lines be drawn so they are not parallel to existing lines and not pass through previous points of intersection. Consider now the addition of a third line L shown below which intersects the two previous lines at the points P1 and P2, and subdivides the previous 3 regions 2, 3 and 4, into 6 regions 2-a, 2-b, 3-a, 3-b, 4-a, and 4-b, giving rise to a total of 7 regions.

In general, if we have already drawn n - 1 lines giving rise to S_n-1 subregions, then the addition of the nth line will intersect the previous n - 1 lines and pass through n previous regions, dividing these n regions into 2n regions. Hence, the total new number of regions S_n will be

S_n = S_n-1 + n

for n = 2, 3, ... . And since we can determine S_n for any n. The following table illustrates for different values of S_n.

n	Sn
1	2
2	2 + 2 = 4
3	4 + 3 = 7
4	7 + 4 = 11
5	11 + 5 = 16
6	16 + 6 = 22
7	22 + 7 = 29
8	29 + 8 = 37
9	37 + 9 = 46

To determine a general formula for S_n and not just one that relates S_n to S_n-1, we repeatedly use the formula

Sn	= Sn-1 + n
	= Sn-2 + (n + 1) + n
	= Sn-3 + (n - 2) + (n - 1) + n
	... ... ...
	= S1 + 2 + 3 + 4 + ... + n
	= 1 + (1 + 2 + 3 + ... + n)
	= 1 + n (n + 1)/2
	= (n2 + n + 2)/2

[Previous]	Problem 7 (Equal Perimeter Problem)
[Next]	Problem 9 (Mary's Random Walk)
[Up]	February Solutions
[Home]	Home Page
[Mail]	Send EMail to Maine Math Talent Search
[Contents]	Maine Math Talent Search Contents

Last modified on Wednesday, March 17, 1999