National Math Olympiad in Slovenia

The greatest number of vertices that can be painted red is $\frac{n+1}{2}$. If we paint $\frac{n+1}{2}$ consecutive vertices of the $n$-gon, then the condition is satisfied.

Now, assume that we have painted at least $\frac{n+1}{2}+1$ vertices. Let us denote the vertices of the $n$-gon in order using positive integers from $1$ to $2k+1=n$. We have assumed that at least $k+2$ vertices are red. Consider the pairs $(1, k+1)$, $(2, k+2)$, $(3, k+3)$, ..., $(k, 2k)$, $(k+1, 2k+1)$, which determine some of the longest diagonals of the $n$-gon. There are precisely $k+1$ pairs and each vertex is contained in one of them, so there exists at least one pair in which both vertices are red.

Without loss of generality we may assume that the red pair is $(1, k+1)$, renumbering the vertices if necessary. There are at least $k$ red vertices remaining, but there are only $k-1$ numbers $2, 3, ..., k$. So, at least one of the vertices numbered $k+2, k+3, ..., 2k+1$ must be red. Assume that the red vertex is $k+m$ where $2 \le m \le k+1$. The vertex $k+m$ lies on the same side of the line through $1$ and $k+1$ as the centre of the $n$-gon. We conclude that the centre of the $n$-gon lies inside the triangle with vertices $1, k+1, k+m$, since the segment with endpoints $1, k+1$ is one of the longest diagonals of the $n$-gon. But the vertices $1, k+1, k+m$ are all painted red, so the centre of the $n$-gon lies inside a triangle with red vertices.