IMO Shortlist

A line is said to be red if it contains two points of $M$. As no three points of $M$ are collinear, each red line determines a unique pair of points of $M$. Moreover, there are precisely $\binom{n}{2} < \frac{n^{2}}{2}$ red lines. By the value of a segment we mean the number of red lines intersecting it in its interior, and the value of a set of segments is defined to be the sum of the values of its elements. We will prove that (i) the value of the initial set of segments is smaller than $n^{3} / 2$ and that (ii) each step decreases the value of the set of segments present by at least 2. Since such a value can never be negative, these two assertions imply the statement of the problem.

To show (i) we just need to observe that each segment has a value that is smaller than $n^{2} / 2$. Thus the combined value of the $n$ initial segments is indeed below $n \cdot n^{2} / 2 = n^{3} / 2$.

It remains to establish (ii). Suppose that at some moment we have two segments $AB$ and $CD$ sharing an interior point $S$, and that at the next moment we have the two segments $AC$ and $BD$ instead. Let $X_{AB}$ denote the set of red lines intersecting the segment $AB$ in its interior and let the sets $X_{AC}$, $X_{BD}$, and $X_{CD}$ be defined similarly. We are to prove that $|X_{AC}| + |X_{BD}| + 2 \leqslant |X_{AB}| + |X_{CD}|$.

As a first step in this direction, we claim that
$$|X_{AC} \cup X_{BD}| + 2 \leqslant |X_{AB} \cup X_{CD}|. \tag{1}$$
Indeed, if $g$ is a red line intersecting, e.g. the segment $AC$ in its interior, then it has to intersect the triangle $ACS$ once again, either in the interior of its side $AS$, or in the interior of its side $CS$, or at $S$, meaning that it belongs to $X_{AB}$ or to $X_{CD}$ (see Figure 1). Moreover, the red lines $AB$ and $CD$ contribute to $X_{AB} \cup X_{CD}$ but not to $X_{AC} \cup X_{BD}$. Thereby (1) is proved.

Figure 1

Figure 2

Figure 3

Similarly but more easily one obtains
$$|X_{AC} \cap X_{BD}| \leqslant |X_{AB} \cap X_{CD}|. \tag{2}$$
Indeed, a red line $h$ appearing in $X_{AC} \cap X_{BD}$ belongs, for similar reasons as above, also to $X_{AB} \cap X_{CD}$. To make the argument precise, one may just distinguish the cases $S \in h$ (see Figure 2) and $S \notin h$ (see Figure 3). Thereby (2) is proved.

Adding (1) and (2) we obtain the desired conclusion, thus completing the solution of this problem.