1
$\begingroup$

Assuming there are n points on a circle, then there are $C_n^2$ chords. If any three chords don't intersect in circle. How to show the circle will be divided into $1+ C_n^2 + C_n^4$ domains?

Picture below is a example of 5 points on circle.

enter image description here

$\endgroup$
  • 1
    $\begingroup$ Contest math? Can you give a link or otherwise make sure that the contest is not currently running. We have a strict policy not to discuss on-going contests $\endgroup$ – Jyrki Lahtonen Jan 3 at 9:13
  • $\begingroup$ Anyway, I would try induction on $n$. Add another point, draw the new chords, and for each and every one of them determine how many other chords it intersects with. Then determine how many "old" regions are split in two by the "new" chords and apply the induction hypothesis. I haven't done the details. Possibly familiarity with standard summation formulas is required. In other words, adapt this thinking to your case. $\endgroup$ – Jyrki Lahtonen Jan 3 at 9:18
  • $\begingroup$ Not ruling out the possibility that a sleek answer exists :-) Anyway, if you are in contest training, you are expected to be familiar with (or to familiarize yourself with) that simpler variant. $\endgroup$ – Jyrki Lahtonen Jan 3 at 9:21
2
$\begingroup$

Induction proof

Base step: For a single point, there is only one region. This is what the formula $1 + \binom 12 + \binom 14$ says as well, so we're good.

Induction step: Say the formula is correct for $n = k$. Now take the figure for $k$ points, and add another point. How many new regions did we make? Well, for each of the $k$ new chords we draw, we can find out how many regions it cut into two new regions, and add them together.

Below is a picture for $k = 5$, with old points in red, old chords in blue, the new point in green (the lowest one), and the new chords in purple.

enter image description here

How many regions does one of the new chords divide? If you look at the drawing you can convince yourself that it's the number of old chords it intersects (not counting the chords that share an end point) plus 1. And the new chord intersects an old chord if and only if the end points of the old chord are on opposite sides of the new chord. So the number of old chords that a new chord intersects is simply the number of old points to its left multiplied by the number of points to its right (again, not including its end point).

Let's label the new chords $1$ through $k$, from left to right. As an example, chord number $1$ (the leftmost new chord) has no old points on its left and four on its right, so it intersects $0\cdot 4 = 0$ chords and therefore makes $0 + 1$ new regions. Chord number $3$, on the other hand (the middle new chord), has two old points on its left and two new points on its right, and therefore intersects $2\cdot 2 = 4$ chords, meaning it makes $4+1 = 5$ new regions. In general, for chord number $i$, there are $i-1$ old points on its left and $k-i$ old points on its right, so it intersects $(i-1)(k-i)$ chords and thus makes $(i-1)(k-i) + 1$ new regions.

Thus the number of regions for $n = k+1$ is $$ 1 + \binom k2 + \binom k4 + \sum_{i = 1}^k \big[ (i-1)(k-i) + 1 \big]\\ = 1 + \binom k2 + \binom k4 + \sum_{i = 1}^k(ik - i^2 - k + i + 1)\\ = 1 + \binom k2 + \binom k4 + k\binom {k + 1}2 - \frac{k(k+1)(2k+1)}{6} - k^2 + \binom {k+1}2 + k $$ where I've used the well-known formulas for sums of consecutive integers and sums of consecutive squares. In here we have $1$ and we have a $\binom{k+1}2$, so for this to be equal to what we want, namely $1 + \binom{k+1}2 + \binom{k+1}4$, the only thing left is to prove that the remaining terms match up. In other words that $$ \binom k2 + \binom k4 + k\binom {k+1}2 - \frac{k(k+1)(2k+1)}6 - k^2 + k= \binom{k+1}4 $$ Here one can just insert, calculate and check. Or one can simplify a bit first, using $\binom{k+1}4 = \binom k3 + \binom k4$, and then insert and calculate: $$ \binom {k}2 + k\binom {k+1}2 - \frac{k(k+1)(2k+1)}6 - k^2 + k= \binom k3\\ \frac{k^2 - k}2 + \frac{k^3+k^2}{2} - \frac{2k^3+3k^2 + k}{6} - k^2 + k= \frac{k^3 - 3k^2 + 2k}{6} $$ Confirming that this is indeed true is not very difficult.


Alternative proof

This problem also has a nice solution using the Euler characteristic. I'll give a summary of the solution in that video here.

Your drawing is a planar graph, where the original $n$ points, along with any intersection between chords are the vertices, and all the resulting line segments from intersection to intersection, as well as the cicrle arcs between the original points, are the edges. Euler's characteristic formula then says that $F$, the number of regions inside your circle, is $$ F = E - V + 1 $$ where $V$ is the number of vertices and $E$ is the number of edges. (Note that in the Wikipedia article and the video I linked above, the region outside the circle is also counted, which is why they have $+2$ at the end instead of $+1$. We don't want to count that one, so I threw it out from the get-go.)

So, how many vertices and edges do we have?

I'll start with the number vertices. First there are the original $n$ points. in addition there are all th intersections between the chords. How many intersections are there? Well, there is exactly one intersection for each quadruple of originaal points. So that's $\binom n4$. In total we get $V = n + \binom n4$.

Then the number of edges. First there are $n$ circle arcs. Then there are the $\binom n2$ chords, which are chopped up. How are they chopped up? Note that each intersection divides two segments into four, increasing the total number of segments by $2$. So there are $\binom n2 + 2\binom n4$ line segments. In total $E = n + \binom n2 + 2\binom n4$.

Inserting that into Euler's formula above, we get $$ F = \binom n4 + \binom n2 + 1 $$ which is what we were after.

$\endgroup$

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.