3

If I have N circles, where every circle intersects every other circle at 2 distinct points, then the number of disjoint regions equals the number of intersections + 1.

I would like to know if there is a nice intutive reasoning to why this is true.

edit: To clear up, every circle intersects every other circle and every pair of intersection points is unique. So you cannot have something like this

enter image description here

60q
  • 87

2 Answers2

3

Hint. Think inductively. Suppose you have a configuration with $n$ circles and the right number of regions and intersections. Now add another circle. How many new intersections are there? How have new regions been created?

Start by drawing a fourth circle in your three circle picture.

Edit in response to comment.

Suppose the answer is right for $n$ circles. Imagine the next one. It meets each of the old circles twice, so there are $2n$ new intersections, all on the new circle. Those intersections divide the new circle into $2n$ arcs. Each of those arcs cuts an old region in two, so there are $2n$ new regions. That says the answer is right for $n+1$ circles.

You can get the result directly from Euler's formula:

Suppose there are $n$ circles. Each meets the other $n-1$ twice, so contains $2(n-1)$ vertices that cut it into that many arcs. The total count of arcs is thus $2n(n-1)$. The total count of vertices is half that since each vertex appears on two circles. Then $$ 1 = V - E + F = n(n-1) - 2n(n-1) + F $$ so $$ F = 1 + n(n-1) = 1 + V. $$

Ethan Bolker
  • 95,224
  • 7
  • 108
  • 199
  • Hmm, this was the original problem I was trying to solve (What is the maximum number of regions we can create by adding a new circle). And I concluded that when you added a new circle, you would always increase the number of intersections by the number of existing circles. The number of new regions it creates, however, I could not find (without using the idenity we are trying to prove). – 60q Nov 30 '22 at 02:46
  • I am trying to say that, I have unfortunately already tried to find how many new regions it creates for some time and gotten nowhere. – 60q Nov 30 '22 at 02:49
  • Looking at how each arc cuts a region into 2 is exactly what I was missing. – 60q Dec 01 '22 at 19:01
1

Well, Let $a_n$=Number of Regions for number of circle drawn till n step

Define $b_n$=Increment of number of regions from $a_{n-1}$ to $a_n$ Thus $b_{n+1}-b_{n}$ is actually constant because speed of increment does not depend on n as it means the new circle cuts each of the previous regions into 2, implying $b_n=2(n-1) $ thus But $b_n=a_{n}-a_{n-1}=2(n-1)$ thus Thus $a_n={n(n-1)}+1$

Now, for $n$ circles we get two distinct points for each pair of circle so total number of point is $2$$n\choose 2$$=\frac{n(n-1)}{2}$ $\blacksquare$

N.B: This is a very philosophical argument think it deeply it took me about 4hrs to visualize.

Thanks to 60q for his comment!!!!

  • I don't understand why the speed of increment = how many points, pairs of circles intersect at. – 60q Dec 01 '22 at 20:23
  • @60q speed of increment is 2 it's because it's any circle drawn divides each previous region in 2, I must edit that Thanks. I hope this makes sense now. –  Dec 02 '22 at 12:44