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

3 Answers 3

5
$\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$
5
  • $\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
    Commented Jul 21, 2015 at 16:52
  • $\begingroup$ @laurent: I noticed it and fixed it. $\endgroup$ Commented Jul 21, 2015 at 16:56
  • 1
    $\begingroup$ @JackD'Aurizio - nice illustration! Vote up! $\endgroup$ Commented Jul 21, 2015 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$ Commented Jul 21, 2015 at 17:12
  • $\begingroup$ @Jack, saw your update just now. Pl ignore my earlier comment. $\endgroup$ Commented Jul 21, 2015 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$
0
$\begingroup$

The maximal number of intersection points inside the circle occurs when no three of our segments pass through the same point inside the circle. Now consider one of the intersection points and the two segments which meet at it. These two segments are the diagonals of a quadrilateral which has the endpoints of the two segments as its vertices. This is true for every intersection point inside the circle. Moreover, it is true that if we select any four of the nine given points on the circle, connecting them will form a quadrilateral whose diagonals provide one intersection point inside the circle. Therefore, our problem becomes one of counting the number of ways to pick 4 of the 9 points, which can be done in C (9,4) = 126 ways.

$\endgroup$
1
  • 1
    $\begingroup$ Welcome to Mathematics. It seems to me that your post is similar to the accepted answer. Can you please edit it and explain better your point? $\endgroup$ Commented Nov 13, 2019 at 11:50

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .