Two or more spots are placed anywhere on a circle's circumference. Every pair is joined by a straight line. Given n spots, what is the maximum number of regions into which the circle can be divided?

I vaguely remembered this problem from a problem solving course I took a few years back.  The point the instructor was trying to make was not to jump to conclusions.

First a chart for n=1...9 points

n f(n)

0 1

1 1

2 2

3 4

4 8

5 16

6 31

7 57

8 99

9 163

When working this out by hand the totals seem to be powers of two until you reach n=6 when it stops rising so quickly.  You can find the finite differences of these terms to see that it is actually a polynomial:

sequence: 1, 1, 2, 4, 8, 16, 31, 57, 99, 163...

1st differences: 0, 1, 2, 4, 8, 15, 26, 42, 64...

2nd differences: 1, 1, 2, 4, 7, 11, 16, 22...

3rd differences: 0, 1, 2, 3, 4, 5, 6...

4th differences: 1, 1, 1, 1, 1, 1...

So it is a 4th degree polynomial with first coefficient =1/(4!)

I continued to find this polynomial by hand, but to make a long story short I got f(n) = (1/24)n^4 - (1/4)n^3 + (23/24)n^2 - (3/4)n + 1

I'm not sure how to actually PROVE this is actually a polynomial situation, but I hand checked n=10 and n=11 and this formula continues to work.

I also found some other interesting patterns in counting up the number of regions each point adds for a given n.  I haven't been able to make much of this yet.

For example for n=9  you start with 1 region (the circle) when you connect the first point with each other point you add (1+1+1+1+1+1+1+1)=8 more regions, connecting the second point with each point not already connected to it adds (1+2+3+4+5+6+7)=28 new regions. Next comes (1+3+5+7+9+11)=36, (1+4+7+11+15)=35, (1+5+9+13)=28, (1+6+11)=18, (1+7)=8, (1)=1.

This demonstrates (proves?) why the result is a polynomial:  f(n) is the sum of several sums of sequences.   I tried using this pattern to come up with a formula but I kept getting bogged down.

-Jer

Posted by Jer on 2004-12-27 21:50:14