79
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Henning Makholm Feb 16 '17 at 9:10
  • 2
    $\begingroup$ Please, recalculate your table. For 3 circles there are 7 regions, for 4 circles 11... $\endgroup$ – Jaroslaw Matlak Feb 16 '17 at 9:16
  • 7
    $\begingroup$ See the related OEIS sequence $\endgroup$ – mbomb007 Feb 16 '17 at 19:25
  • 1
    $\begingroup$ @pgblu: it has to be independent of the radius, by scaling. (So long as all the circles have the same radius, of course) $\endgroup$ – smci Feb 16 '17 at 20:18
  • 5
    $\begingroup$ @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. $\endgroup$ – M. Winter Feb 16 '17 at 21:48
93
$\begingroup$

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$.

$\endgroup$
  • 6
    $\begingroup$ This is IMHO the way to do it. Using complex numbers makes many a thing simpler to see, but it is not necessary. I want to encourage all readers to study inversions aka reflections w.r.t. a circle. $\endgroup$ – Jyrki Lahtonen Feb 17 '17 at 7:14
  • $\begingroup$ So Christian's hint turns the question into this older one. The solution to that is essentially the one in Glen O's answer. $\endgroup$ – Jyrki Lahtonen Feb 17 '17 at 7:16
82
$\begingroup$

Imagine 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.

$\endgroup$
  • $\begingroup$ Beautiful answer! Love the graph-theoretical approach :) $\endgroup$ – Chandler Watson Feb 18 '17 at 3:06
  • $\begingroup$ Euler characteristic is the canonical way to solve this problem in my opinion. $\endgroup$ – Arthur Feb 19 '17 at 9:15
51
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ I think this answer is the most obvious and straightforward, especially since the OP specifically mentioned looking for a pattern. $\endgroup$ – mbomb007 Feb 16 '17 at 19:23
20
$\begingroup$

What I find amusing, is that you don't need to fill the circumference. In fact you will get the same exact number of sectors in these 2 different ways of placing circles:

Overlapping circles in different ways

But in the first (left) case, reasoning on the number of sectors is much easier. Seems in some way you found an "invariant" for circles.

Now by looking at the left picture you will recognize the pattern for sure, Seems you where looking for a "visualization" rather than a simple algebric proof.

Unlucky choice of startin number of circles

And here it is:

$$3(k-1) + 1$$

Where $k$ is number of circles of course. For $1$ circle it holds. It does not hold for $2$ circles (or for $3$ or $5$). The fact is that I was unlucky in choosing $4$ as starting number of circles.

Well let's see why, just focusing on the external region:

highligted external region of crossing circles.

Each added circle will go through 1 extra circle compared to previous circles. That is nothing more than "half square" made of squares. I don't remember the exact formula for that, but since we are given already the number of circles why not use it directly?

$$\frac{(k-1)(k-2)}2$$

So the total number of sectors inside the circle is:

$$2(k-1) + \frac{(k-1)(k-2)}2 + 1$$

Now this time we got something that holds for any number of circles above $3$.

  • $0$ Circles: hardcoded $0$ regions
  • $1$ Circle: hardcoded $1$ region
  • $2$ Circles: hardcoded $3$ regions
  • $3$ Circles: $(2\times2) + (1) + 1 = 5$ regions
  • $4$ Circles: $(2\times3) + (3) + 1 = 10$ regions
  • $5$ Circles: $(2\times4) + (6) + 1 = 15$ regions

This is not a real proof, but helps visualization which is what OP asked for. :)

$\endgroup$
  • 2
    $\begingroup$ +2 if counting also the plane (any similitude with "+1 upvote comments" is purely casual). $\endgroup$ – GameDeveloper Feb 18 '17 at 2:57
  • 3
    $\begingroup$ +1 for a visualization that can be understood without needing more math than is required to pose the question in the first place. Combined with the sequence of values from @Glen-o 's answer you've got an answer suitable for young children as well as those who're familiar with algebra. $\endgroup$ – Dan Neely Feb 19 '17 at 22:25
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I find it beautiful that C(n, 2) is n(n-1)/2 $\endgroup$ – KevinOrr Feb 18 '17 at 7:31
0
$\begingroup$

In order to state what you want to prove, and get some intuition about the problem, you may join the dark side of the force (and use Maxima).

As it looks like polynomials, 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

So, it really looks like a polynomia, and we even have a formula. So we may be tempted to detect some induction

(%i7) expand(g(x) - g(x-1));
(%o7)                                  x

Looks fine. So back to the geometry to establish the proof.

[Of course the computations are easy in this problem, and may be conducted by hand. But in more complex problems, playing with symbolic computation / solver software may help a lot].

$\endgroup$
  • 1
    $\begingroup$ Do you feel no obligation to prove anything? Or is the hand-waving “Looks like polynomials” enough for you? $\endgroup$ – PJTraill Feb 23 '17 at 14:34
  • $\begingroup$ Well, of course not, but the proofs provided by other contributors were more than enough for me. But before getting into a proof, you have to gather some intuition about the problem. And formulate what you want to prove. In this case, examination of the first values can be done by hand easily (looking at the differences), but the point is, using a solver may provide some help in less obvious cases. Looking at the figures, inducing a general rule, and then trying to establish a correspondence between terms and elements of the problem. $\endgroup$ – Michel Billaud Feb 24 '17 at 8:18
  • $\begingroup$ OK, I see where you were coming from – perhaps an introductory motivational sentence would have been useful to clarify that. There is certainly an interesting variety of approaches in the answers given. You pays your money and you takes your choice! $\endgroup$ – PJTraill Feb 24 '17 at 9:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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