3
$\begingroup$

There are 9 points on the circumference of a circle. The points are not evenly spaced. Line segments are drawn connecting each pair of points. What is the largest number of different points inside the circle at which at least two of these line segments intersect?

Here is what I am attempted trying to solve this problem. With 3 points on the circumference there will not any point of intersection. With 4th point I have 1 point of intersection. With 5 points I am getting 5 points of intersection (shape looking like a star with one spoke missing). 6th point make the total go up to 15. Do I need to keep counting this way or there is better method? Also I am failed to understand how evenly spaced or unevenly spaced points would have made a difference.

$\endgroup$
4
$\begingroup$

With $9$ points on the circle, there are $\binom{9}{2}=36$ line segments.

How many couples of line segments share a vertex? For every vertex, there are $8$ line segments with such an endpoint, hence there are $9\cdot\binom{8}{2}=252$ couples of line segments with a common endpoint, and at most:

$$\binom{36}{2}-9\cdot\binom{8}{2} = 378 $$ points of intersection not on the circle. In general, with $n$ points on the circle there are at most: $$ \binom{\binom{n}{2}}{2}-n\cdot\binom{n-1}{2} = \frac{n(n-1)(n-2)(n-3)}{8}=3\binom{n}{4}$$ points of intersection not on the circle. Inside the circle, there are just $\color{red}{\binom{n}{4}}$ points of intersection: every choice of four points on the circle is associated with a unique internal point of intersection. So with $9$ points on the circle there are at most $\color{red}{126}$ internal points of intersection.

You just have to choose where to place these $n$ points in such a way that no triple of line segments is concurring, i.e. you have to prove that you can arrange them in general position to achieve this maximum:

$\hspace2in$enter image description here

$\endgroup$
  • $\begingroup$ For 4 points, some of the crossings have to occur out of the circle... So you cannot always achieve the maximum of $3{n \choose 4}$. $\endgroup$ – laurent Jul 21 '15 at 16:52
  • $\begingroup$ @laurent: I noticed it and fixed it. $\endgroup$ – Jack D'Aurizio Jul 21 '15 at 16:56
  • 1
    $\begingroup$ @JackD'Aurizio - nice illustration! Vote up! $\endgroup$ – johannesvalks Jul 21 '15 at 17:05
  • $\begingroup$ With 4 points there can be only one point of intersection however way we try to place the points - correct? Your formula 3* C(n,4) will give us 3. Am I missing out anything? $\endgroup$ – user3138594 Jul 21 '15 at 17:12
  • $\begingroup$ @Jack, saw your update just now. Pl ignore my earlier comment. $\endgroup$ – user3138594 Jul 21 '15 at 17:14
0
$\begingroup$

Every pair of points divides the set of remaining points into two sets (let say $L$ and $R$ for points left of the segment and right of the segment). Then, the segment formed by these two points will cross internally the segments with one end in $R$ and one end in $L$. There are exactly $|L| \cdot |R|$ such segments.

The size of $L$ is something between 0 and $n-2$.

A segment for which $|L| = 0$ will have no internal crossing. There are $n$ such segments.

A segment for which $|L| = k$ will have $k(n-2-k)$ crossings. There are $n$ such segments.

In the end each crossing is counted twice so you are looking for

$$ \frac{n}{2}\sum_{k=0}^{n-2} k(n-2-k).$$

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