6. In how many ways can the vertices of a polygon with $n \geq 3$ sides be colored using three colors such that there are exactly $m$ sides, $2 \leq m \leq n$, with endpoints of different colors?
Solution. In the polygon, we mark the midpoints of the $m$ sides whose endpoints must be colored with different colors. This can be done in $\left(\begin{array}{l}n \\ m\end{array}\right)$ ways. The $n$ vertices of the polygon are thus divided into $m$ groups of consecutive vertices, all of which have the same color, but the vertices of adjacent groups have different colors. There are then as many ways to color these groups as there are ways to color a polygon with $m$ sides such that no side has endpoints of the same color (which is actually the special case $m=n$ of the problem; this interpretation is also valid if $m=2$ considering the "polygon" with 2 vertices connected by a double side). The solution will then be $\left(\begin{array}{l}n \\ m\end{array}\right) C_{m}$, where $C_{m}$ is this number.

We will obtain $C_{m}$ by finding a recurrence relation for these numbers. Obviously, $C_{2}=C_{3}=6$. Suppose then $m \geq 4$ and fix three consecutive vertices $P_{1}, P_{2}, P_{3}$. If $P_{1}$ and $P_{3}$ are colored differently, we can directly connect them, eliminating $P_{2}$, resulting in a polygon with $m-1$ sides to be colored in the indicated manner. Conversely, each of these colored polygons will give rise to one with $m$ sides (the color of $P_{2}$ will be determined by those of $P_{1}$ and $P_{3}$), thus contributing $C_{m-1}$ possibilities to $C_{m}$. On the other hand, if $P_{1}$ and $P_{3}$ have the same color, we can glue them together, eliminating $P_{2}$, resulting in a polygon with $m-2$ sides that we will have to color. Each of these colorings will now give rise to 2 colorings for the original polygon (since there will be 2 possibilities for $P_{2}$), and thus the contribution to $C_{m}$ in this case is $2 C_{m-2}$. We thus find the desired recurrence relation: $C_{m}=C_{m-1}+2 C_{m-2}$.

From the above relation, we can easily obtain the first values of $C_{m}$, $m \geq 2: 6,6,18,30,66,126, \ldots$ If we compare this sequence with that of the powers of $2: 4,8,16,32,64,128, \ldots$, it seems obvious that $C_{m}=2^{m}+(-1)^{m} 2$, a formula that can be easily confirmed by induction. Indeed, the formula is correct for $C_{2}$ and $C_{3}$ and, if $m \geq 4$,

$$
C_{m}=C_{m-1}+2 C_{m-2}=2^{m-1}+(-1)^{m-1} 2+2\left(2^{m-2}+(-1)^{m-2} 2\right)=2^{m}+(-1)^{m} 2
$$

Therefore, the solution is $\left(\begin{array}{l}n \\ m\end{array}\right)\left(2^{m}+(-1)^{m} 2\right)$.