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.
Best Answer
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$