All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Shapes > Geometry
Circle and Spots (Posted on 2004-12-27) Difficulty: 4 of 5
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?

No Solution Yet Submitted by SilverKnight    
Rating: 3.0000 (6 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution I come up with something else Comment 9 of 9 |

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

Please log in:
Remember me:
Sign up! | Forgot password

Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (3)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information