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 20041227 21:50:14 