Shaovalov A.v.

Two players take turns coloring the sides of an $n$-gon. The first player can color a side that borders with zero or two colored sides, the second player - a side that borders with one colored side. The player who cannot make a move loses. For which $n$ can the second player win, regardless of how the first player plays?
For $n=3$, it is obvious that the first player wins, while for $n=4$, the second player wins. Let's show how the first player wins when $n>4$. After the first move of the second player, two adjacent sides are painted. The first player can paint a side "one apart" from them, creating an unpainted "hole" of one side. This is his sanctuary, which the second player cannot paint. The first player uses the sanctuary only if he has no other move. If such a moment comes (the second player may lose earlier), then (after "closing" the sanctuary) the unpainted part will consist of pairs of adjacent sides. From then on, the first player can always respond to the second player's move by painting a side from the same pair.

## Answer

Only for $n=4$.