## Task 2.

Each side and each diagonal of some convex $n$-gon is colored in one of $k$ colors. It is known that there is no monochromatic closed broken line whose vertices are also vertices of the given polygon. What is the largest possible value of the number $n$?
## Solution.

It is known that a graph with $n$ vertices that does not contain a cycle has at most $n-1$ edges. This fact can be easily proven by induction on the number of vertices $n$. Therefore, at most $n-1$ edges (i.e., sides and diagonals) can be colored with the same color.

Since the number of colors is $k$, and the total number of edges (i.e., sides and diagonals) is $\frac{n(n-1)}{2}$, we conclude that

$$
\frac{n(n-1)}{2} \leqslant (n-1) k, \quad \text { i.e., } n \leqslant 2 k
$$

We will show that for any natural number $k$, we can color the sides and diagonals of a regular $2k$-gon with $k$ colors such that there is no monochromatic closed broken line (without loss of generality, we can consider a regular polygon since it only matters how the edges are colored). Moreover, we will show that each of the $k$ colors can be used to color exactly $2k-1$ sides and diagonals in the desired manner.

Let the vertices of the regular $2k$-gon be denoted by $A_{1}, A_{2}, \ldots, A_{2k}$. Color one color the broken line $A_{1} A_{2k} A_{2} A_{2k-1} \ldots A_{i} A_{2k+1-i} \ldots A_{k} A_{k+1}$, as shown in the following figure.

![](https://cdn.mathpix.com/cropped/2024_05_30_59f140c89de2d58a74e9g-21.jpg?height=703&width=814&top_left_y=1573&top_left_x=612)

Each subsequent color $j, j \in \{2, \ldots, k\}$ is used to color the broken line obtained by rotating the mentioned one by an angle of $\frac{j \pi}{k}$ around the center of the polygon. The broken lines thus obtained are mutually disjoint, otherwise, some diagonal would remain uncolored, which is not possible.

Therefore, the maximum possible value of $n$ is $2k$.