Monday

August 3, 2015

August 3, 2015

Posted by **Seth** on Sunday, August 27, 2006 at 3:33pm.

My question for you.... If you use six lines, what is the MAXIMUM number of regions into which you can divide the plane?

See if you can improve on this.

http://fredd-e.narfum.org/boc/assets/img/bocmath_misc03.gif

In the general case,

Maximum regions =(n^2+n+2)/2

where the n means number of lines.

You need to prove this to yourself using your drawings for n=1, n=2, 3, 4, 5, and 6.

What happens if each line intersects the other -once of course- and no three intersect at the same point? I.e., extend the sides of a triangle indefinitely. This requires that no 2 lines be parallel and no 3 intersect at the same point. I think (I didn't verify this yet) that's how the maximum might be achieved. I also think there should be (n(n-1))/2 vertices with this approach, so some experimenting with 3,4 and 5 lines should suggest a formula for how many regions are formed.

Regions Created by Crossed Lines Within a Circle

A popular problem in the field of recreational mathematics revolves around the ever popular division of an area into the maxomum number of regions. It traditionally seeks the number of regios a circle can be cut into by any number of straight lines no three of them intersecting at a single point.

The derivation of the number of regions created within different shaped figures comes in a variety of forms. Consider the following variations.

1--Irregular convex polygons divided into regions by connecting each vertex with every other vertex by straight lines.

2--Circles divided into regions by connecting "n" randomly located points on the circumference with each other by straight lines without any three lines passing through the same point. This is essentially joining all "'n" points in sequence and creating all the inner diagonals between the points.

3--Circles divided up by a series of lines that cross one another within the circle without any three lines passing through the same point. This is the same as the #2 variation with the exception that the points of intersection of the lines on the circumference are not joined to one another.

It is immediately obvious that the connection of "n" randomly located points by straight lines within the circle is simply the polygonal n-gon inscribed in a circle. Therefore, the number of regions created within the circle is the number of regions defined within the n-gon plus the "n" arc/chord regions created when inscribing the n-gon within the circle.

Eliminating the lines joining the adjacent points on the circumference, the chords, creates the familiar pizza puzzle where you are asked to determine the number of pieces a round pizza can be cut into with "n" straight line cuts across the pizza, without any three lines passing through the same point. In other words, how many regions are created with the increasing number of "n" lines? Lets explore.

Draw a circle and draw the diameter. Obviously, the circle is divided into two regions, or slices.

Draw another line crossing over the first line, Clearly, we can see that we now have four regions.

Draw a third line crossing over both of the previous two lines. Once again, we can readily see that we now have 7 regions.

Draw a fourth line crossing over the previous three lines. It is still fairly easy to see that we now have 11 regions

Draw a fifth line crossing over the previous four lines. With a little care, we can see that we now have 16 regions.

Lets step back and see what we have so far.

Lines.......Regions....Difference

...0...............1................-

...1...............2...............1

...2...............4...............2

...3...............7...............3

...4..............11..............4

...5..............16..............5

What can we learn from this information? It is immediately obvious that with each increase in the number of lines, we gain an identical number of regions, i.e., we add a fifth line and we add 5 regions. Another careful observation tells us that each number of regions is simply the sum of 1 plus the sum of the lines used up to that point. 1 = 1 + 0, 2 = 1 + 1, 4 = 1 +3, 7 = 1 + 6, 11 = 1 + 10, and 16 = 1 + 15. You might now recognize that the sums added to the 1 each time are simply the triangular numbers, the sums of the integers from 1 to n, being defined by Tn = n(n + 1)/2. Therefore, if we call the number of lines "n", the "n" lines will divide the circle up into Rn = 1 + n(n + 1)/2 = [n^2 + n + 2]/2. We can now extend our tabular data to

Lines.......Regions....Difference

...0...............1................-

...1...............2...............1

...2...............4...............2

...3...............7...............3

...4..............11..............4

...5..............16..............5

...6..............22..............6

...7..............29..............7

...8..............37..............8

...9..............46..............9

..10.............56.............10

...n......[n^2+n+2]/2........n

Another way of deriving this expression results from the analysis of the particular sequence of numbers that the data creates. Looking at the preliminary data again, we have

n = lines..........1.....2.....3.....4.....5

N = regions.....2.....4.....7....11...16

Taking the successive differences we get

n = lines..........1.....2.....3.....4.....5.....6.....7

N = regions.....2.....4.....7....11...16

1st Diff................2.....3.....4.....5

2nd Diff..................1......1.....1

With the 2nd differences being constant, we recognize that we have a finite difference sequence with 2nd differences equal to 1. Therefore, the general expression for N in terms of "n" is of the form N = an^2 + bn + c. Using the data, we can write

a(1^2) + b(1) + c = 2 or a + b + c = 2

a(2^2) + b(2) + c = 4 or 4a + 2b + c = 4

a(3(2) + b(3) + c = 7 or 9a + 3b + c = 7

Solving, a = 1/2, b = 1/2 and c = 1 leading to N = n^2/2 + n/2 + 1 = (n^2 + n + 2)/2, the same as we deduced earlier.