## Task A-1.5.

A convex polygon with 2022 vertices is given, where no three diagonals intersect at the same point. It is necessary to color some diagonals red so that at least one red diagonal emanates from each vertex.

What is the smallest possible number of intersections (at a vertex or in the interior) of the red diagonals?
## Solution.

We will prove that the smallest number of intersections Marko can achieve is 2.

Let $A_{1}, A_{2}, \ldots, A_{2022}$ denote the vertices of the given polygon in order.

First, we provide an example of drawing red diagonals such that exactly two intersections are achieved. Draw the diagonals $\overline{A_{1} A_{3}}$ and $\overline{A_{2} A_{4}}$, which intersect. Then draw the mutually parallel diagonals

$$
\overline{A_{2022} A_{5}}, \overline{A_{2021} A_{6}}, \ldots, \overline{A_{1011} A_{1016}}
$$

Finally, draw the diagonals $\overline{A_{1012} A_{1014}}$ and $\overline{A_{1013} A_{1015}}$ which intersect each other. This gives us an example with a total of 2 intersections.

We will prove that we always have at least two intersections. Assume the contrary, that there is an example of drawing diagonals in which there are at most one intersection, and consider that example.

Consider two points $A_{i}, A_{j}$ that are neither adjacent nor opposite, i.e., neither $|i-j|=1$ nor $|i-j|=1011$. We will say that a point $A_{k}$ lies between $A_{i}$ and $A_{j}$ if it lies in the smaller of the two parts of the polygon determined by the line $A_{i} A_{j}$.

Among all the diagonals Marko has drawn, choose the one that connects vertices between which there are the fewest other vertices—let's call this the shortest diagonal. Without loss of generality, this diagonal is of the form $\overline{A_{1} A_{k}}$, where $k \leqslant 1012$ (otherwise, we can rotate the numbering of the points and reflect the polygon across the line $A_{1} A_{1012}$). Consider the points $A_{2}, \ldots, A_{k-1}$. These are the endpoints of diagonals that connect vertices between which there are more or at least as many other vertices as for the diagonal $\overline{A_{1} A_{k}}$, so each of these points is the endpoint of some diagonal that intersects the diagonal $\overline{A_{1} A_{k}}$. Since the polygon has at most one intersection, we conclude that $k=3$, and the diagonal $\overline{A_{1} A_{k}}$ intersects the diagonal $\overline{A_{2} A_{m}}$ for some index $m$. Without loss of generality, $m \leqslant 1013$.

We will prove that $m=4$. Assume that $m \geqslant 5$. All diagonals with one endpoint in the set $\left\{A_{4}, A_{5}, \ldots, A_{m-1}\right\}$ must have their other endpoint in this set. Otherwise, that diagonal would intersect the diagonal $\overline{A_{2} A_{m}}$. Among all such diagonals, choose the shortest one: let it be $\overline{A_{k} A_{l}}$. Similarly as before, all vertices between $A_{k}$ and $A_{l}$ are endpoints of diagonals that are not shorter than the diagonal $\overline{A_{k} A_{l}}$, so they must intersect it, thus giving us two intersections. Therefore, it must be that $m=4$.

Choose again the shortest diagonal in the polygon, different from $\overline{A_{1} A_{3}}$ and $\overline{A_{2} A_{4}}$: let it be $\overline{A_{k} A_{l}}$. If there is a point between $A_{k}$ and $A_{l}$ different from $A_{1}, A_{2}, A_{3}$, and $A_{4}$, we can again conclude that there is some diagonal that intersects $\overline{A_{k} A_{l}}$. Therefore, we conclude that the diagonal $\overline{A_{k} A_{l}}$ is precisely $\overline{A_{2022} A_{5}}$.

We can repeat this argument: the next shortest diagonal in the polygon is $\overline{A_{2021} A_{6}}$, then $\overline{A_{2020} A_{7}}, \ldots$, and so on until $\overline{A_{1519} A_{508}}$. The last diagonal is a diagonal connecting opposite vertices of the polygon, so it is the longest possible diagonal. Since by construction this is the shortest diagonal up to this point, we conclude that all remaining diagonals are of equal length, i.e., they connect opposite vertices of the polygon. However, all such diagonals pass through the center of the polygon, thus giving us at least one more intersection. This contradicts the assumption that Marko can draw diagonals such that there is at most one intersection.

We conclude that the smallest number of intersections of diagonals is indeed 2.

## NATIONAL MATHEMATICS COMPETITION

## 2nd grade - high school - A variant

Vodice, May 11, 2022.