Dividing a Circle using Six Lines

Date: 08/29/2001 at 11:35:27
From: Jordy G
Subject: Geometry

What is the largest number of regions into which you can divide a 
circle with six lines? Is there a formula? How can you get this 
answer? I've tried drawing diagrams but I can't find a way to make 
sure they are correct. I can only get 14, but I know there are more.

Date: 08/29/2001 at 14:29:41
From: Doctor Rob
Subject: Re: Geometry

Thanks for writing to Ask Dr. Math, Jordy.

There is a formula.  For n lines, you can get at most

   (n^2+n+2)/2

regions.  When n = 6, this gives 22 regions.

To maximize the number of regions, draw your lines like this:

Start with one line. Label the two points where it meets the circle as 
P1 and Q1.

Pick points P2 and Q2 such that they are encountered in the order 
P1,P2,Q1,Q2,P1 going around the circle clockwise. Connect P2 and Q2 to 
make the second line, and four regions.

Between P2 and Q1 pick point P3. Between Q2 and P1 pick point Q3.  
Connect them with a line, but, if necessary, move Q3 a little to make 
sure that the line does not pass through any of the intersections of 
any previously drawn lines. That will give you seven regions.

Between P3 and Q1 pick point P4. Between Q3 and P1 pick point Q4. 
Connect P4 to Q4 with a line, but, if necessary, move Q4 a little to 
make sure that the line does not pass through any of the intersections 
of any previously drawn lines. That will give you 11 regions.

Continue in this way until you have 6 lines and 22 regions.

P1-P6 and Q1-Q6 can be chosen to be 12 adjacent vertices of a regular 
n-gon inscribed in the circle, if n > 12. It is easy to construct a 
regular 16-gon by starting with a diameter of the circle and bisecting 
the central angles until they are all equal to 360/16 = 22.5 degrees.  
That will locate 16 equally-spaced points around the circumference of 
the circle. Pick any 12 that are adjacent, and label them P1, P2, ..., 
P6, Q1, ..., Q6. Then connect P1Q1, P2Q2, ..., P6Q6. If you have done 
this carefully, you will be able to see and count the 22 regions.

- Doctor Rob, The Math Forum
  http://mathforum.org/dr.math/   

Date: 08/29/2001 at 17:01:10
From: Doctor Greenie
Subject: Re: Geometry

Hi, Jordy -

There is a formula - as I see another doctor here has already shown 
you.

But there is a way you can get the answer without the formula, by 
logically analyzing what happens as you draw more and more lines.  
And, if you know the correct mathematical techniques, this logical 
analysis can lead you to a derivation of the formula.

I have always found mathematics to be more enjoyable when I can see 
where a formula comes from, rather than having to regard it as some 
sort of mathematical magic.

So here is how you can analyze this problem, at least far enough to 
come up with the answer to your problem.

You are going to analyze how and when the number of regions increases 
as you draw more lines through the circle. You will find that, if you 
think of actually physically drawing each line, the number of regions 
increases by one at a time; each increase is the result of an existing 
region being cut into two separate regions.

Start with a circle; before you draw any line through the circle, it 
is a single region.

Now, start drawing the first line through the circle, and consider at 
what point(s) you add another region to the diagram. When you are 
almost all the way from your starting point to the other side of the 
circle, there is still only one region; it is not until you reach the 
other side that you have divided an existing region (in this case, the 
entire circle) into two parts. So, when you draw the first line 
through the circle, there is one point at which one of the existing 
regions becomes two regions: when you reach the opposite side of the 
circle. So we have:

   1st line drawn through circle ==> number of additional regions = 1

Next, start drawing the second line through the circle, and consider 
at what point(s) you add another region to the diagram. Of course, 
since you want to create the largest number of regions in the circle, 
you want your second line to intersect the first line inside the 
circle. So you start at some point on the circle, and when you reach 
the first line somewhere inside the circle you have added another 
region by dividing an existing region into two parts. And then when 
you reach the other side of the circle you have again added another 
region by dividing an existing region into two parts. So, when you 
draw the second line through the circle, there are two points at 
which one of the existing regions becomes two regions: when you reach 
the first line you drew, and when you reach the opposite side of the 
circle. So we have:

   2nd line drawn through circle ==> number of additional regions = 2

Now, start drawing the third line through the circle, and consider at 
what point(s) you add another region to the diagram. Of course, since 
you want to create the largest number of regions in the circle, you 
want this third line to intersect both of the first two lines at 
different points inside the circle (if your third line intersects the 
first two lines at their point of intersection, you don't get the 
maximum possible number of regions). So you start at some point on the 
circle, and when you reach the first line somewhere inside the circle 
you have added another region by dividing an existing region into two 
parts, and when you reach the second line you have again added another 
region. And when you reach the other side of the circle you have again 
added another region by dividing an existing region into two parts.  
So, when you draw the third line through the circle, there are three 
points at which one of the existing regions becomes two regions: when 
you reach each of the the first two lines you drew, and when you reach 
the opposite side of the circle. So we have:

   3rd line drawn through circle ==> number of additional regions = 3

I think you can see where the analysis will go from here....

When you draw the n-th line, you create n new regions -- (n-1) new 
regions, one for each time you intersect one of the previous (n-1) 
lines that you drew, and a last time when you reach the other side of 
the circle.

So you can answer your specific question by making a simple table

     number of   number of   total number
       lines    new regions   of regions
    --------------------------------------
        0            --            1
        1             1            2
        2             2            4
        3             3            7
        4             4           11
        5             5           16
        6             6           22

Then there are various mathematical techniques (which I won't go into 
here) for examining the sequence of the number of regions

    1, 2, 4, 7, 11, 16, 22, ...

to come up with the formula for the maximum number of regions formed 
by n lines:

                              n^2+n+2
    # regions with n lines = ---------
                                 2

- Doctor Greenie, The Math Forum
  http://mathforum.org/dr.math/   

Date: 08/29/2001 at 21:13:47
From: Anonymous
Subject: Re: Geometry

Thank you so much!