4. [7] At each of two round tables, there are $n$ gnomes sitting. Each gnome is friends only with their neighbors to the left and right at their table. A kind wizard wants to seat the gnomes at one round table so that every two neighboring gnomes are friends. He has the ability to make $2 n$ pairs of gnomes friends (the gnomes in a pair can be from the same table or different tables), but after that, an evil wizard will make $n$ pairs of these $2 n$ pairs enemies. For which $n$ can the kind wizard achieve his goal, no matter how the evil wizard acts?

(Mikhail Svyatlovsky)
Answer: for all odd $n>1$.

Let $A_{1}, A_{2}, \ldots, A_{n}$ be the gnomes sitting at the first table, and $B_{1}, B_{2}, \ldots, B_{n}$ be the gnomes sitting at the second table.

Case of odd $n$. Let $n=2 k-1$. The good wizard's strategy: to befriend pairs of gnomes $\left(A_{i}, B_{i}\right)$ and $\left(A_{i}, B_{i+1}\right)$ (here we assume that $\left.B_{2 k}=B_{1}\right)$. Clearly, the good wizard has befriended exactly $2 n$ pairs of gnomes. Let's check that with this strategy, the evil wizard cannot interfere with the good one.

Indeed, since the evil wizard quarrels exactly half of the specified pairs, either among the pairs $\left(A_{i}, B_{i}\right)$ at least $k$ still remain friends, or among the pairs $\left(A_{i}, B_{i+1}\right)$ at least $k$ still remain friends. Then, in the first case, there will be an $i$ for which both pairs of gnomes $\left(A_{i}, B_{i}\right),\left(A_{i+1}, B_{i+1}\right)$ are still friends, and the good wizard can seat them at the table as follows: $A_{i}, B_{i}, B_{i-1}, \ldots, B_{i+1}, A_{i+1}, A_{i+2}, \ldots, A_{i-1}$. The second

![](https://cdn.mathpix.com/cropped/2024_05_06_5a5226ecdafaa0b597fdg-3.jpg?height=265&width=679&top_left_y=377&top_left_x=1300)
case is analogous.

Case of even $n$. We will provide a strategy for the evil wizard. Suppose the good wizard has already somehow befriended $2 n$ pairs of gnomes; construct a graph where the vertices correspond to the gnomes, and the edges correspond to the pairs of gnomes that the good wizard has befriended. Color the gnomes at the first table in white and black in a checkerboard pattern, and at the second table in red and blue. Since the sum of the degrees of all vertices is $4 n$, there will be a color for which the sum of the degrees of the vertices colored in this color does not exceed $n$. Without loss of generality, this is the white color, that is, the gnomes $A_{1}, A_{3}, \ldots, A_{n-1}$. Suppose the evil wizard quarrels all pairs of friends that include white gnomes. Then the only remaining friends of any white gnome $A_{2 l+1}$ are his old neighbors $A_{2 l}$ and $A_{2 l+2}$, and it is clear that the good wizard cannot seat all the gnomes at one table in the required manner.