Maths Olympiad Prep

Library / /13 of 31

Geometry Difficulty 6.0 National olympiad Prove it Belarus

Palina marked 20212021 arbitrary points on the circle and drew 20212021 segments between them. By an intersection point we denote any point of intersection of two drawn segments if this point is the endpoint of none of them.
Find the maximal possible number of intersection points. (Mikhail Karpuk)

Solution

20211009=20391892021 \cdot 1009 = 2039189.
Let's solve the problem for an arbitrary odd number nn of marked points and drawn segments. We enumerate the marked points on the circle by the numbers from 11 to nn in the order of going around the circle. For each i=1,{n}i = 1, \overline\{n\} we denote by aia_i the number of drawn segments for which ii is an endpoint. Among all ({n)}{2}\binom\{n\}\{2\} pairs of segments, at least ({a)i}{2}\binom\{a_i\}\{2\} pairs do not intersect, since they have a common endpoint ii. For different i=1,{n}i = 1, \overline\{n\} these pairs do not coincide, hence the number of intersection points does not exceed
M=({n)}{2}(({a)1}{2}+({a)2}{2}++({a)n}{2}). M = \binom\{n\}\{2\} - \left( \binom\{a_1\}\{2\} + \binom\{a_2\}\{2\} + \dots + \binom\{a_n\}\{2\} \right).
Let's determine the largest possible value of MM, for which we find the smallest possible value of the sum in brackets. It is easy to see, by opening the brackets, that the inequality ({b)}{2}+({a)}{2}>({b)1}{2}+({a)+1}{2}\binom\{b\}\{2\} + \binom\{a\}\{2\} > \binom\{b-1\}\{2\} + \binom\{a+1\}\{2\} is equivalent to the inequality b1>ab-1 > a. Therefore, the numbers ai,i=1,{n}a_i, i = 1, \overline\{n\}, must differ at most by one. Given that a1+a2++an=2na_1 + a_2 + \dots + a_n = 2n, it's only possible if a1=a2==an=2a_1 = a_2 = \dots = a_n = 2. Hence, the maximum possible value of MM is equal to {n(n1)}{2}n={n(n3)}{2}\frac\{n(n-1)\}\{2\} - n = \frac\{n(n-3)\}\{2\}.
To make sure that this value is the answer for the problem, we provide an example. Let's arrange points at the vertices of a regular nn-gon and sequentially perform the following operation with each of them: choose a point ii and consider the set pip_i of intersection points of all possible segments with vertices at the remaining points. The set pip_i is finite, and the set of points on the arc containing the point ii is infinite. Therefore, we can choose such a new location for it that no segment connecting the point ii with any other point passes through the points of the set pip_i. As a result of such operations, we obtain an arrangement of points such that no three segments with vertices at these points have a common point inside the circle. Now it suffices to draw segments connecting the points with numbers ii and i+[n/2]i + [n/2], i=1,{n}i = 1, \overline\{n\}, (we assume that the numbers are cyclic modulo nn, i.e. n+k=kn + k = k if k=1,{n}k = 1, \overline\{n\}). In this case, any two segments that don't have a common endpoint, intersect and all aia_i are equal to two.
Substituting the value n=2021n = 2021 into the found formula {n(n3)}{2}\frac\{n(n-3)\}\{2\}, we find the answer 20211009=20391892021 \cdot 1009 = 2039189.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.