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?

Suppose that N-1 points located (in order) around a circle have all been connected yielding S(N-1) sectors. What is the effect of adding the Nth point? We'll break this question down into determining the number of new sectors added when we connect points N and K for K=1..N-1.

When we connect N with K we cross each of the lines (J,K+1) to (J, N-1) for J=1,..K-1 [Note: lines are given as (x,y) with x<y]. That is, we cross (K-1)(N-K-1) lines. Each time we cross a line, we add one sector. We also add a sector when we reach the point K. Hence, adding the line (K,N) leads to (K-1)(N-K-1)+1 new sectors. Thus:

S(N) = S(N-1) + Sum{K=1 to N-1} [ (K-1)(N-K-1) + 1 ]

But (K-1)(N-K-1) + 1 = -K^2 + NK + (2 – N) so

S(N) = S(N-1) + (N-1)(N^2 – 5N + 12)/6

Also S(1) = 1 so

S(N) = 1 + Sum{L=1 to N} (L-1)(L^2 – 5L + 12)/6

S(N) = (N^4 – 6N^3 + 23N^2 – 18N + 24)/24

S(N) starts off growing like 2^(N-1) before slowing down. The first few terms of S(N) are 1,2,4,8,16,31,57

Edited on February 6, 2008, 12:25 am

Posted by FrankM on 2008-01-19 12:43:05