## Task 2.

A natural number $n$ is good if we can color each side and diagonal of a regular $n$-gon in some color so that for any two vertices $A$ and $B$, there is exactly one vertex $C$, different from $A$ and $B$, such that the segments $\overline{A B}, \overline{B C}$, and $\overline{C A}$ are colored the same color.

Determine which of the numbers $7,8,9,10,11$, and 12 are good, and which are not.
## Solution.

The numbers 8, 10, 11, and 12 are not good, while 7 and 9 are.

First, we show that even numbers are not good. Assume that $n$ is a good number and consider a fixed vertex $A$ of a regular $n$-gon colored in the prescribed manner. For each other vertex $B$, there is a unique vertex $C$ such that the sides of triangle $ABC$ are monochromatic. In other words, all vertices different from $A$ can be paired. Therefore, $n$ must be odd, and the numbers 8, 10, and 12 are not good.

Furthermore, we show that not all numbers of the form $n=3k+2$ are good. Assume that $n$ is a good number and that the regular $n$-gon is colored in the prescribed manner. Let $t$ be the number of triangles $ABC$ in which all sides are monochromatic. For each such triangle, there are three pairs of monochromatic sides, while for each pair of vertices of the $n$-gon, there is a unique triangle with monochromatic sides. Therefore,

$$
3t = \frac{n(n-1)}{2}
$$

so 3 divides $n$ or $n-1$, meaning that numbers of the form $n=3k+2$ (including 11) are not good.

Finally, we will show by construction that 7 and 9 are good numbers. The vertices of a regular $n$-gon will be labeled by the numbers $1, 2, \ldots, n$, and we will list the triples that determine triangles with monochromatic sides. There must be $t = \frac{n(n-1)}{6}$ triples, and for each pair of distinct numbers $a, b \in \{1, 2, \ldots, n\}$, there must be exactly one triple of which $a$ and $b$ are members.

For $n=7$, we have $t=7$ triples: $(1,2,3), (1,4,5), (1,6,7), (2,4,6), (2,5,7), (3,4,7)$, and $(3,5,6)$.

For $n=9$, we have $t=12$ triples: $(1,2,3), (4,5,6), (7,8,9), (1,4,7), (2,5,8), (3,6,9), (1,5,9)$, $(2,6,7), (3,4,8), (1,6,8), (2,4,9)$, and $(3,5,7)$.