Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given $n$ circles of possibly different radii, how many distinct regions can there be? For small $n$, I can work it out with pictures. (I'm pretty sure $n=4$ can yield 13 distinct regions, but not positive.)

Just curious what an approach to the problem could be.

E.g. I have considered that is could be a quadratic sequence based on skimpy evidence, but don't know why that would be, or how to prove it.

I would also be interested to know if there was a way of doing this problem with regular $n$-gons. (I am assuming that there would be more regions, but am not sure.)

share|improve this question
    
With two n-gons you can get $2n+1$ regions by having the centers match and clocking one by $\frac{\pi}{n}$ –  Ross Millikan May 18 '11 at 0:56
    
I understand, but as you get more I think (but am not sure) you can do better by varying the size of the n-gons –  soandos May 18 '11 at 0:59
    
I don't think you can do better for only 2. You want to maximize the number of intersection points. This approach generalizes to $mn+1$ for $m$ n-gons, but eventually a quadratic approach will dominate. –  Ross Millikan May 18 '11 at 1:03
    
But for more than 2? –  soandos May 18 '11 at 1:11
    
For more than 2, the proof for circles goes through. Note I left out the exterior above, so two n-gons can give $2n+2$. Two n-gons can intersect in $2n$ points, so if you have $m$ already, the $m+1^{\text{st}}$ can intersect in $2mn$ points, adding $2mn$ regions. In total, for $m$ n-gons, we get $2+m(m-1)n$ regions, where for circles $n=1$ instead of $\infty$. –  Ross Millikan May 18 '11 at 3:05
add comment

2 Answers

up vote 2 down vote accepted

OEIS gives the number of regions for circles. It gets 14 for 4 circles, including the exterior. The general formula is $n^2-n+2$. Allowing different size circles doesn't help. The proof is by induction. With one circle there are $2$ regions. Assuming the formula is true for $n$, the new circle can cross old ones in at most $2n$ points. Each segment can cut an existing region in two parts, adding $2n$ regions. So the maximum number of regions for $n+1$ circles is $n^2-n+2+2n=(n+1)^2-(n+1)+2$

share|improve this answer
    
Exterior meaning the space occupied for no circles? You might want to edit your post to include the formula... In addition, does this mean any sized circles, or all the same size? –  soandos May 18 '11 at 1:03
    
@soandos: Yes, "exterior" does mean the space occupied by no circles, so your "13" is correct. Also, as the OEIS entry makes no mention of the size of the circles, I think it's any sized circles. –  El'endia Starman May 18 '11 at 1:12
    
Do you know why this formula works? –  soandos May 18 '11 at 1:18
    
@Ross: Change to reflect necod's comment (listed as answer as he does not have enough rep) –  soandos May 18 '11 at 2:19
    
@soandos: Note that Ross's solution is correct for $n$ circles in a plane; OEIS lists $n^2 + n +2$ as the maximum number of regions created by $(n+1)$ circles (which Ross computes in his proof by induction, with result matching OEIS result for $n + 1$ circles. See oeis.org/A002061 for the formula for n such circles (given by Ross). –  amWhy May 18 '11 at 16:06
show 4 more comments

The source quoted by Ross Millikan (OEIS) gives different formula:

$$n^2+n+2$$

share|improve this answer
    
Thank you for noticing. –  soandos May 18 '11 at 2:19
2  
That is off by 1 from what you would think, as stated in the OEIS notes. 1 circle gives 2 regions, not 4. I changed the sign of the middle term to minus to account for that in my proof. –  Ross Millikan May 18 '11 at 2:57
    
@Ross, @necod: please see my comment above this answer for more details. –  amWhy May 18 '11 at 16:07
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.