2
$\begingroup$

$n$ points ($n>1$) are taken on the circumference of a circle. Through any two of them a chord is drawn. No three chords intersect at one point inside the circle. i) Find how many points of intersections of these chords are inside the circle? ii) Find how many parts do these chords divide the circle?

I know one solution is to make a graph and use Euler's formula $v-e+f=2$. But that idea I would have never come up with. Is there any other way to approach this?

$\endgroup$
  • $\begingroup$ The number of separate parts inside the circle is a sequence that starts $1,2,4,8,16,\ldots$. Can you guess the next term? $\endgroup$ – Arthur Sep 2 '16 at 20:14
  • $\begingroup$ 32. How do you prove formally that the sequence gives the parts inside the circle? $\endgroup$ – Amrita Sep 2 '16 at 20:52
  • 1
    $\begingroup$ It's actually 31. I was deliberately trying to throw you off. I don't know how to prove it, but Euler characteristic seems like a not-too-bad idea. $\endgroup$ – Arthur Sep 2 '16 at 20:54
0
$\begingroup$

An arrangement of $s$ lines are drawn in the plane so that no three lines intersect at a common point and no two lines are parallel. Now circumscribe this arrangement by a circle so that all intersections are in the interior of the circle. Denote the circumscribed line arrangement by $\mathcal{H}_{1,s}$ and call it a "circle line arrangement". I write the number of points, edges and faces of $\mathcal{H}_{1,s}$ as $\varphi_{0}(s)$, $\varphi_{1}(s)$, and $\varphi_{2}(s)$ respectively. The degrees or valency of any point $p$ in the arrangement is the count of line segments incident to the point and is denoted, $deg(p)$.

claim 1:$\text{ }$$\varphi_{0}(s) = \frac{s(s+3)}{2}$

Proof: Since each of the $s$ lines intersects the boundary of the circle, in exactly two distinct places there are $2s$ boundary points. Furthermore since any two distinct lines intersect and no three lines determine a point, equivalently all points are pairwise distinct there are exactly $\binom{s}{2}$ interior points. Summing up the interior and boundary points we get: \begin{equation}2s + \binom{s}{2} = \frac{s(s+3)}{2}\end{equation}

Claim 2: $\text{ }\varphi_{1}(s)=s(s+2)$

Proof: We can partition points into two distinct sets $\bigcup_{i=1}^n R_{i}$ and $\mathcal{R}_{0}$ representing interior and boundary points respectively. For brevity write $I = \bigcup_{i=1}^n R_{i}$. Points in the interior of the arrangement are the intersection of two distinct lines and consequently are incident to four line segments. Equivalently every interior point has degree equal to four and there are $\binom{s}{2}$ such interior points. If $p$ is on the boundary of the arrangement then $p$ is determined uniquely by a line which intersects the boundary of the circle. In this case we have the line segment incident to $p$ and the two circular arcs that are incident to the point and so $deg(p)=3$ and there are $2s$ such points. I use a result from Euler to do the calculation: \begin{align*} 2\varphi_{1}(s)&= \sum_{p\in {R}_{0}}deg(p) + \sum_{p\in I}deg(p)\\ &=4\binom{s}{2}+3(2s)\\ &=2s(s-1)+6s\\ &=2s^{2}+4s \end{align*}Division by 2 gives us $\varphi_{1}(s) = s(s+2)$.

claim 3:$\text{ }\varphi_{2}(s)=\frac{s^{2}+s+4}{2}$

Proof: I bring Euler's characteristic equation $\varphi_{0}(s)-\varphi_{1}(s) +\varphi_{2}(s)=\chi$ into play and recall that for planar graphs $\chi$ = 2. Regrouping and then substituting terms gives us $$\varphi_{2}(s) = 2 + \varphi_{1}(s) - \varphi_{0}(s) =2 + s(s+2) - \frac{s(s+3)}{2} =\frac{s^{2}+s+4}{2}$$

$\endgroup$
  • $\begingroup$ I assumed no chords could be parallel $\endgroup$ – Antonio Hernandez Maquivar Sep 2 '16 at 21:15
  • $\begingroup$ In the question n points were given on circumference, not s lines. Here s is not given. Is s = ${n \choose 2}$ $\endgroup$ – Amrita Sep 2 '16 at 22:01

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.