Investigating Sequence Patterns

Date: 05/14/98 at 00:59:00
From: Daniela Condo
Subject: Regions in circles (investigation)

This is an investigation we gave to our Year 8 maths students:

You have a circle. You put 3 dots on the circumference and connect 
them with all possible straight lines, forming a certain number of 
regions (in the case of 3 dots, there are 4 regions). By putting an 
ever-increasing number of dots on the circumference, you have to try 
to find a pattern in the number of dots and the number of regions 
formed. Unfortunately, we could find no substantial pattern.

Here is the table of results:

  dots      1   2   3   4   5   6   7   8    9   10   11   12
  regions   1   2   4   8  16  30  57  88  163  230  386  456

At first there seemed to be a pattern involving the Fibonacci 
sequence:
  
       dots       regions
        2            2        = 2*1
        3            4        = 3*1+1
        4            8        = 4*2
        5           16        = 5*3+1
        6           30        = 6*5
        7           57        = 7*8+1
        8           88        = here is where it started to go wrong

We tried matching an exponential regression line to it, but it was not 
accurate. We even looked for patterns in the odd and even numbers of 
dots, thinking maybe it was a piecewise function; or patterns in the 
differences of the factors....

This investigation is being assessed, and any light you could shed on 
it would be greatly appreciated!

Date: 05/15/98 at 12:07:20
From: Doctor Schwa
Subject: Re: Regions in circles (investigation)

Wow, that's quite a lot of data. Did you draw a really big circle and 
try to count them? I would get tired way before this. Or did you have 
some other method of producing this table? If so, the method you used 
might be a good clue for uncovering the pattern. Also, not knowing 
where you got these big numbers makes me wonder if there might be some 
small mistake, and as you already know, even if you're just off by 1 
you could hide a beautiful pattern.

Noticing the Fibonacci sequence connection is a very nice start. I 
wouldn't have noticed that pattern at all, though Fibonacci does make 
some sense here because the pattern you unearthed is really subtle and 
hard to see. 

I'll do my best to help, but you've already used such a great set of 
problem solving strategies I don't know if I'll be able to do 
much better.

Here are your data one more time to refresh my memory:

   dots      1   2   3   4   5   6   7   8    9   10   11   12
   regions   1   2   4   8  16  30  57  88  163  230  386  456

I hope you were careful in drawing your dots not to make any special 
patterns with them (e.g. a regular hexagon, where several lines all 
pass through the point in the middle, will have fewer regions than
if you used a nonregular hexagon).

The way I start working on a problem like this is to draw a picture 
of my own. It's clear why 1 dot does nothing new, and just leaves 
1 circle. The second dot lets you draw one line, cutting the circle in 
half. The third dot lets you draw two lines, cutting two new regions.
The fourth dot lets you draw two lines to adjacent dots, each of which 
cut one new region, and one line to the opposite dot, which crosses a 
line on the way there so it makes 2 new regions, and we get 
1 + 1 + 2 = 4 new regions all told.

So then I start wondering if I can make a pattern out of that. I don't 
see it yet, so I scribble a couple more cases on my picture. The fifth 
dot connects to two adjacent dots again, making one new region each, 
and now there are two "opposite" dots, and I have to cross two lines 
on the way there, so they make a total of three new regions each, for 
1 + 1 + 3 + 3 = 8 new regions.

So now I guess the pattern: when I add the sixth dot, I'll get 1 + 1 
for the adjacent two dots I connect to, 4 + 4 for connecting to the 
two dots next to them, and then 5 for connecting to the opposite 
vertex. That means I added 15, so I get 31 regions for 6. Maybe you 
did the problem with a regular hexagon? Or some other kind of shape 
where more than two lines crossed at one point? Or you missed counting 
one region? Or maybe I made a mistake?  If I did, let me know.

Supposing I'm right so far, the pattern does get pretty complicated.
I always add 1 + 1 for connecting to the two adjacent vertices, then 
(n-2) + (n-2) for the two next to that but it's tricky to count how 
many crossings I make going to the next vertices.

The way I think of it is that the number of new regions created is the 
number of connections I cross, plus 1. Each vertex to the left of the 
line I draw has to connect to each vertex to the right of the new line 
I draw. So when I draw that 7th dot, I get two adjacent dots giving 
1 + 1, the two next to that (splitting the other 5 dots into groups of 
1 and 4) gives me (4+1) + (4+1), and the remaining two (splitting the 
other 5 dots into groups of 2 and 3) gives me (2*3 + 1) + (2*3 + 1)
so all told I get 2 + 10 + 14 = 26 new regions. So my number for 7 
dots would be 31 + 26 = 57. Looks like I'm back into agreement with 
you!

There may well be a simple pattern where I could find, say, the answer 
for 100 dots without having to carefully add up everything along the 
way, but if there is, I don't see it now. I could try a bunch of messy 
algebra to express this summation formula, but that doesn't seem as if 
it would be fun. And even if it turned out to be fun, it doesn't sound 
particularly promising.

But perhaps this method of counting will let you generate a few more 
numbers in the list (and check, and correct some of the numbers you 
already have? Again, unless I'm misinterpreting the problem...) and 
maybe once you have a correct table you'll be able to find some 
pattern that I'm not seeing yet.

I think the method of finite differences is very promising. In fact, 
just with the data we already have (if I'm right about the 31?):

     1   2   4   8   16  31  57
       1   2   4   8   15  26
         1   2   4   7   11

where in each row I subtract the two numbers above it. I think a 
complete solution to the problem is not too far away at that point.

If you'd like to talk about this problem some more, please do
send me an email. This kind of problem solving is a lot of fun.

Or, if you'd like to see a more formal treatment, look at 

  Counting Regions Formed by Chords of a Circle
  http://mathforum.org/dr.math/problems/shah5.19.98.html   

-Doctor Schwa,  The Math Forum
Check out our web site! http://mathforum.org/dr.math/