4. A regular $n$-gon, where $n$ is an odd number greater than 1. What is the maximum number of vertices that can be painted red so that the center of the $n$-gon does not lie inside the polygon determined by the red vertices?

## 58th Mathematical Competition for High School Students in Slovenia  Maribor, April 12, 2014

## Problems for 3rd Year

Solve the problems independently. You have 210 minutes for solving.

![](https://cdn.mathpix.com/cropped/2024_06_07_2324ea98e20bf8c655d1g-04.jpg?height=160&width=417&top_left_y=363&top_left_x=1499)
The use of notes, literature, or a pocket calculator is not allowed.
II/4. The largest number of vertices that can be painted red is $\frac{n+1}{2}$. If we paint $\frac{n+1}{2}$ consecutive vertices of an $n$-gon, the condition of the problem is satisfied. Now, suppose we paint at least $\frac{n+1}{2}+1$ vertices. Let the vertices of the $n$-gon be labeled consecutively with natural numbers from 1 to $2k+1=n$. Thus, at least $k+2$ vertices are red. Consider the pairs of vertices $(1, k+1), (2, k+2), (3, k+3), \ldots, (k, 2k), (k+1, 2k+1)$, which represent some of the longest diagonals of the $n$-gon. Since there are exactly $k+1$ such pairs and they cover all vertices, there is at least one pair in which both vertices are red. We can assume this pair is $(1, k+1)$, otherwise, we would just renumber the vertices. Since at least $k$ of the remaining vertices are red, and the vertices numbered $2, 3, \ldots, k$ are only $k-1$ in number, at least one of the vertices numbered $k+2, k+3, \ldots, 2k+1$ is red. Let this vertex be $k+m$, where $2 \leq m \leq k+1$. The vertex $k+m$ lies on the same side of the line determined by vertices 1 and $k+1$ as the center of the $n$-gon. From this, it follows that the center 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 red, so the center of the $n$-gon also lies inside the polygon determined by the red vertices.