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 N1 points located (in order) around a circle have all been connected yielding S(N1) 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..N1.
When we connect N with K we cross each of the lines (J,K+1) to (J, N1) for J=1,..K1 [Note: lines are given as (x,y) with x<y]. That is, we cross (K1)(NK1) 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 (K1)(NK1)+1 new sectors. Thus:
S(N) = S(N1) + Sum{K=1 to N1} [ (K1)(NK1) + 1 ]
But (K1)(NK1) + 1 = K^2 + NK + (2 – N) so
S(N) = S(N1) + (N1)(N^2 – 5N + 12)/6
Also S(1) = 1 so
S(N) = 1 + Sum{L=1 to N} (L1)(L^2 – 5L + 12)/6
S(N) = (N^4 – 6N^3 + 23N^2 – 18N + 24)/24
S(N) starts off growing like 2^(N1) 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 20080119 12:43:05 