49th International Mathematical Olympiad Spain

There are at least $\frac{1}{2}(k+1)(k+2)$ points in the intersection set $I$ in view of the condition $n\ge k+2$. For each point $P\in I$, define its order as the number of lines that intersect the open line segment $OP$. By definition, $P$ is red if its order is at most $k$. Note that there is always at least one point $X\in I$ of order $0$. Indeed, the lines in $L$ divide the plane into regions, bounded or not, and $O$ belongs to one of them. Clearly any corner of this region is a point of $I$ with order $0$.

Claim. Suppose that two points $P,Q\in I$ lie on the same line of $L$, and no other line of $L$ intersects the open line segment $PQ$. Then the orders of $P$ and $Q$ differ by at most $1$.

Proof. Let $P$ and $Q$ have orders $p$ and $q$, respectively, with $p\ge q$. Consider triangle $OPQ$. Now $p$ equals the number of lines in $L$ that intersect the interior of side $OP$. None of these lines intersects the interior of side $PQ$, and at most one can pass through $Q$. All remaining lines must intersect the interior of side $OQ$, implying that $q\ge p-1$. The conclusion follows.

We prove the main result by induction on $k$. The base $k=0$ is clear since there is a point of order $0$ which is red. Assuming the statement true for $k-1$, we pass on to the inductive step. Select a point $P\in I$ of order $0$, and consider one of the lines $\ell \in L$ that pass through $P$. There are $n-1$ intersection points on $\ell$, one of which is $P$. Out of the remaining $n-2$ points, the $k$ closest to $P$ have orders not exceeding $k$ by the Claim. It follows that there are at least $k+1$ red points on $\ell$.

Let us now consider the situation with $\ell$ removed (together with all intersection points it contains). By hypothesis of induction, there are at least $\frac{1}{2}k(k+1)$ points of order not exceeding $k-1$ in the resulting configuration. Restoring $\ell$ back produces at most one new intersection point on each line segment joining any of these points to $O$, so their order is at most $k$ in the original configuration. The total number of points with order not exceeding $k$ is therefore at least $(k+1)+\frac{1}{2}k(k+1)=\frac{1}{2}(k+1)(k+2)$. This completes the proof.