Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Suppose I draw $20$ circles in the plane, all passing through the origin, but no two tangent at the origin. Also, except for the origin, no three circles pass through a common point. How many regions are created in the plane?

enter image description here

So I've managed to compile the following table:

Number of Circles $ \rightarrow$ Number of Regions: $0 \rightarrow 1$, $1\rightarrow 2$, $2 \rightarrow 4$, $3 \rightarrow 7$, $4 \rightarrow 11$, $5 \rightarrow 16$

However, I'm not seeing a pattern that will help me establish the number of regions for $n$ circles.
I know that whenever I add a new circle, I'm adding $1$ new region plus a few others that are bounded by the new circle and adjacent circles.
Any advice on how to proceed further?

share|cite|improve this question
1  
Hint: Each new circle cuts each of the previously drawn ones at exactly one point other than the origin. This allows you to count how many existing regions it slices in two, and hence how much the number of regions increases by. – Henning Makholm yesterday
2  
Please, recalculate your table. For 3 circles there are 7 regions, for 4 circles 11... – Jaroslaw Matlak yesterday
4  
See the related OEIS sequence – mbomb007 yesterday
1  
@pgblu: it has to be independent of the radius, by scaling. (So long as all the circles have the same radius, of course) – smci yesterday
4  
@smci The circles can also have different radii. It is not even necessary that the curves are circles! It is just important that the curves intersect only once besides the central common intersection, which is automatically true if the shapes are (non-tangent) circles. You can see this from the graph theoretic proof. – M. Winter yesterday

Imaginge the drawing of your $n$ circles as a plane graph. The intersections of the circles are the vertices, the arcs between the intersections are the edges. You have one central vertex of degree $2n$ and $\frac12 n(n-1)$ other vertices of degree $4$ (here, the tangent condition and the "no three circles intersect in a single point" condition are used). Now we have $$v=\frac12n(n-1)+1$$ vertices and $$e=\frac12 \sum_i{\mathrm{degree}(v_i)} = \frac12\left(\frac12 n(n-1)\cdot 4+2n\right)=n^2$$ edges. Using Euler's polyhedral formula gives $f=e-v+2=\frac12n(n+1)+1$ faces. For $n=20$ you got $211$ faces.

share|cite|improve this answer

A hint:

Move the origin to $\infty$ using the map $z\mapsto{1\over z}$. Then the circles become lines, no two of them parallel, and no three of them going through the same point.

Denote the number of regions created by $n$ lines by $a_n$, and find a recursion for the $a_n$.

share|cite|improve this answer
2  
This is IMHO the way to do it. Using complex numbers makes many a thing simpler to see, but it is not necessary. Such a reader is encouraged to study inversions aks reflections w.r.t. a circle. – Jyrki Lahtonen 18 hours ago
    
So Christian's hint turns the question into this older one. The solution to that is essentially the one in Glen O's answer. – Jyrki Lahtonen 18 hours ago

Other answers focus on the geometry itself, but this answer focuses on the generated sequence, as observed for $n\in[0,5]$.

Two common types of sequence that can arise in questions like these are polynomial and factorial sequences. To check for patterns of the factorial type, one usually attempts ratios of terms (such as $a_n/a_{n-1}$ or $a_n/a_{n-2}$) and seeks a pattern in those ratios.

This sequence, however, looks more polynomial. For these, it can be useful to examine the differences between terms. Consider $b_n=a_n-a_{n-1}$. Now, we have

$$ \begin{array}{c|cccccc} n && 0 && 1 && 2 && 3 && 4 && 5\\\hline a_n && 1 && 2 && 4 && 7 && 11 && 16\\ b_n && - && 1 && 2 && 3 && 4 && 5 \end{array} $$

Immediately, you should see a pattern. $b_n=n$, at least up to $n=5$. And so, we have $a_n=a_{n-1}+n$ (from which it should be relatively easy to find the solution, noting that $a_0=1$).

This invites an obvious interpretation - for each additional circle, you add as many new regions as there are circles. This can help to inform a search for the reason for the observed pattern.

Now, consider what happens when we actually add a new circle to a set of existing circles - for each of the existing circles, it will intersect once outside of the origin. For each intersection, there is a corresponding region being split in two by the new circle. Therefore, there is one additional region for each existing circle... and one for the origin. So when you add the $n$th circle, you add $n$ regions.

(the split occurs along the arc between pairs of consecutive intersection points)

This is consistent with the observed pattern.

share|cite|improve this answer
2  
I think this answer is the most obvious and straightforward, especially since the OP specifically mentioned looking for a pattern. – mbomb007 yesterday

Join the dark side of the force (and use Maxima). Looks like polynomials, so let's try with degree 2

(%i1) f(x) := a*x*x + b*x + c;
(%o2)                       f(x) := a x x + b x + c
(%i2) solve([ f(0) = 1, f(1) = 2, f(2) = 4]);
                                  1      1
(%o2)                       [[b = -, a = -, c = 1]]
                                  2      2

And check the coefficients for other "experimental data"

(%i3) g(x) := ( x + 1) * x / 2 + 1;
                                     (x + 1) x
(%o3)                        g(x) := --------- + 1
                                         2
(%i4) g(3);
(%o4)                                7
(%i5) g(4);
(%o5)                               11
(%i6) g(5);
(%o6)                               16
share|cite|improve this answer

There will be three different feasible regions into which the plane will be divided. These are:

  1. The region between the intersection of two circles.
  2. The region inside a circle, but not bounded by some other circle.
  3. The region not bounded by any circle.

The intersection region can be found out by choosing two circles out of $n$,as $2$ circles will contain one region, so by method of combination: $\binom{n}{2}$

The region inside a circle, but not bounded by second circle will be equal to $n$ (one region for every circle).

Finally, the remaining plane will be the unbounded region.

Therefore, total parts in which $n$ circles divide the plane: $\binom{n}{2}+n+1$. Plugging the value of $n=20$ according to the question, we get number of regions as $211$.

Test case: Consider an intersection of three circles:

enter image description here

(I have denoted the different regions by various colours). It can be noted that these $3$ circles divide the plane into $7$ regions, which agrees with the answer.

share|cite|improve this answer

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.