4
$\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
  • $\begingroup$ The number of points of intersection inside the circle is $\binom n4$, since each set of four points on the circle determines a pair of intersecting chords. $\endgroup$ – bof Aug 3 '19 at 12:08
1
$\begingroup$

I do not think there is a better approach to find the number of parts (part ii) comparing to the Euler's formula. But to use it one should first find the number of vertices and edges, and for this task I do not see how the Euler's formula can help.

For simplicity we disregard the circle arcs and will consider only the graph consisting of line segments connecting the points.

Let $s$ be a segment connecting two points of the circle. The points split the circle in two parts. Let the number of points in one of the parts be $k$. Then the number of points in the other part is $(n-k-2)$. Every segment which connects a point lying in one part with a point lying in the other part will intersect the segment $s$, whereas any segment connecting two points lying in the same part will not intersect $s$. Therefore the overall number of intersection points of the segment $s$ with other segments is $k(n-2-k)$ and the overall number of intersection points on all segments drawn from each of the considered circle points is: $$ v''_n=\sum_{k=0}^{n-2}k(n-2-k)=\frac{(n-1)(n-2)(n-3)}6=\binom{n-1}3\tag1 $$ and the overall number of the intersection points inside the circle is $$ v'_n=\frac n4 v''_n=\binom n4,\tag2 $$ where factor 4 in the denominator accounts for the fact that while summing over all $n$ circle points every internal intersection point is counted 4 times.

To compute the overall number of vertices we shall add the number of the circle points to the obtained result: $$ v_n=v'_n+n=\frac{n(n+1)(n^2-7n+18)}{24}.\tag3 $$

The number of edges can be computed similarly. Observe that the segment $s$ is split by $n_s$ internal intersection points into $n_s+1$ edges therefore: $$ e''_n=\sum_{k=0}^{n-2}[k(n-2-k)+1]=\binom{n-1}3+\binom{n-1}1=\frac{(n-1)(n^2-5n+12)}6,\tag4 $$ and the overall number of the edges inside the circle is $$ e'_n=\frac n2 e''_n=\frac{n(n-1)(n^2-5n+12)}{12},\tag5 $$ where factor 2 in the denominator accounts for the fact that while summing over all $n$ circle points every chord is counted 2 times.

To compute the overall number of edges we shall add the number of arcs connecting the circle points to the obtained result: $$ e_n=e'_n+n=\frac{n^2(n^2-6n+17)}{12}.\tag6 $$ Finally we use the Euler's formula for computing the number of parts inside the circle: $$ f_n=e_n-v_n+1=\frac{n^4-6n^3+23n^2-18n+24}{24}.\tag7 $$

And indeed the latter formula describes - as it should - the OEIS sequence A000127.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ $v'_n=\binom n4$ because a set of four points on the circle corresponds to a pair of intersecting chords, namely, the diagonals of the inscribed quadrilateral determined by those four points. $\endgroup$ – bof Aug 3 '19 at 12:19
  • $\begingroup$ Yes of course. I have however decided to give another derivation to count both vertices and edges in a similar way. $\endgroup$ – user Aug 3 '19 at 16:06
  • $\begingroup$ You can "count both vertices and edges in a similar way" but it seems more efficient to note that when you have counted one you have counted the other, since $$e'_n=\binom n2+2v'_n.$$ $\endgroup$ – bof Aug 3 '19 at 21:39
  • $\begingroup$ If you mean that the identity $e'_n=\binom n2+2v'_n$ follows from the intermediate results (4) and (5), I'm sure it does, but since $e'_n=\binom n2+2v'_n$ is easy to see directly, it's not clear what those intermediate results are needed for. $\endgroup$ – bof Aug 4 '19 at 11:29
0
$\begingroup$

The number of vertices inside the circle is $$\binom n4$$ since each such vertex is determined by a pair of intersecting chords, which are the diagonals of an inscribed quadrilateral determined by four points on the circle.

The number of edges inside the circle is $$\binom n2+2\binom n4$$ since there are $\binom n2$ chords, and the number of edges on each chord is equal to $1$ plus the number of interior vertices on that chord, and each of the $\binom n4$ interior vertices lies on two chords.

There are $n$ vertices and $n$ edges on the circle, so the total number of vertices is $$V=n+\binom n4$$ and the total number of edges is $$E=n+\binom n2+2\binom n4.$$ By Euler's formula, the number of faces inside the circle is $$F-1=E-V+1=\binom n2+\binom n4+1=\frac{n(n-1)(n^2-5n+18)}{24}+1=\frac{n^4-6n^3+23n^2-18n+24}{24}.$$

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

If $U$ is the unit disc centered at the origin consider $n$ chords drawn through the interior of $U$ such that no two chords are parallel and no three chords intersect at the same point. The arrangement graph $G$ induced by the discs and the chords has a vertex for each intersection point in the interior of $U$ and $2$ vertices for each chord incident to the boundary of $U.$ Naturally $G$ has an edge for each arc directly connecting two intersection points.

A point $p$ of $G$ is said to be incident to the interior of $G$ if $p$ is in the interior of $U.$ Similarly $p$ is said be incident to the boundary of $G$ if $p$ is on the boundary of $U.$ In this sense and without loss of generality I speak of the boundary of $U$ as the boundary of $G$ and the interior of $U$ as that of $G.$ I denote the number of arcs incident to $p$ by $v(p),$ called the valency of $p.$ It is straightforward to see that if $p$ is incident to the interior of $G$ then $p$ is $4-$valent. Likewise if $p$ is incident to the interior of $G$ then $p$ is $3-$ valent. From this we see that the maximum valency of $G$ is $4$ and the minimum degree of $G$ is $3.$ By construction $G$ is planar and $3-$ connected.

lemma 1: $G$ has $N(N+3)/2, N(N+2)$ and $(N^2+N+4)/2$ points, arcs and faces respectively.

Each chord has two distinct points incident to the boundary of $G.$ Being there are $N$ such chords it is seen there are $2N$ points along the boundary of $G.$ Observe there are $N(N-1)/2$ points in the interior of $G.$ Indeed the number of points in $G$ is equal to sum of those points in the interior and along the boundary which is $$2N+N(N-1)/2=N(N+3)/2.$$ The number of arcs in $G$ follows from the handshaking lemma. In particular twice the number of arcs is equal to the sum of all valances. The later is equal to $$[3N+4N(N-1)/2]/2=N(N+2)$$ The number of faces in $G$ follows from Euler's characteristic formula for planar graphs.$$2-N(N+3)/2+N(N+2)=(N^2+N+4)/2 $$ This establishes the lemma.

| cite | improve this answer | |
$\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.