## Solution.

The smallest such $k$ is $K:=\frac{n}{2}$ for even $n$, and $K:=\frac{n+1}{2}$ for odd $n$.

Assume first that fewer than $K$ vertices are colored red. Then there are strictly more uncolored vertices than red ones, so there must be two adjacent uncolored vertices.

Since in any triangulation of the polygon, the side connecting these two uncolored vertices must be part of some triangle, we conclude that this triangle has at least two uncolored vertices, meaning it has at most one red vertex.

It remains to find an example of coloring and selection of diagonals in the case where at least $K$ vertices are colored red and there is at least one good triangulation.

One possibility is to start from some vertex (which we color) and alternately color or not color each subsequent adjacent vertex. Then there will certainly be no two adjacent uncolored vertices.

Choose an arbitrary red vertex $C$ and draw all $n-3$ diagonals from it. Then each triangle in this triangulation has $C$ and some two adjacent vertices of the polygon as its vertices. Due to the coloring method, we know that at least one of these two vertices is red, so each triangle has at least two red vertices. Thus, this triangulation is good, and $K$ is the smallest $k$ that satisfies the conditions of the problem.

Note: The form of the number $K$ can also be written as $K=\left\lceil\frac{n}{2}\right\rceil$.

A correct solution without proof is worth 1 point. For a complete solution, it is necessary to prove that $k$ cannot be smaller (5 points) and provide a construction example for the smallest $k$ (4 points).

## ZUPANIJSKO NATJECANJE IZ MATEMATIKE

## 3rd grade - high school - A variant

March 29, 2021.

## IF A STUDENT HAS A DIFFERENT APPROACH TO SOLVING THE PROBLEM, THE COMMITTEE IS OBLIGED TO GRADE AND EVALUATE THAT APPROACH APPROPRIATELY.
## Task A-2.5.

Let $n$ be a natural number. If a regular $n$-gon is divided into $n-2$ triangles by drawing $n-3$ diagonals that do not have common interior points, we say that we have obtained a triangulation. A triangulation of an $n$-gon, some of whose vertices are red, is good if each of those $n-2$ triangles has at least two red vertices.

Determine the smallest natural number $k$, depending on $n$, such that we can color $k$ vertices of a regular $n$-gon red so that there exists at least one good triangulation.