The sides of a dodecagon are numbered $C_{1}, C_{2}, \ldots, C_{12}$. In how many ways can the sides of a dodecagon be colored with four colors so that two adjacent sides are always of different colors? (We consider two colorings to be different as soon as one of the sides $C_{i}$ is colored with two different colors).

翻译结果如上，保留了原文的换行和格式。
We will prove a more general result by induction: how many ways we can color the sides of a polygon with $n$ sides using $k$ colors, such that adjacent sides are of different colors. We denote this quantity as $p_{n, k}$. Let's start coloring our polygon: there are $k$ choices for side $C_{1}$, then $k-1$ possible choices for side $C_{2}$ different from the color of $C_{1}$, and so on. We thus find $k(k-1)^{n-1}$ possible colorings such that adjacent sides are of different colors, except possibly $C_{1}$ and $C_{n}$. But the set of incorrect colorings where $C_{1}$ is the same color as $C_{n}$ is clearly in bijection with the set of legal colorings of a polygon with $n-1$ sides (we have merged $C_{1}$ and $C_{n}$). We thus obtain the following recurrence formula: $p_{n, k}=k(k-1)^{n-1}-p_{n-1, k}$.

Since $p_{3, k}=k(k-1)(k-2)$, we have

$$
p_{n, k}=k(k-1)^{n-1}-k(k-1)^{n-2}+\ldots+(-1)^{n-4} k(k-1)^{3}+(-1)^{n-3} k(k-1)(k-2)
$$

thus

$$
\begin{aligned}
p_{n, k} & =k \frac{(k-1)^{n}+(-1)^{n-4}(k-1)^{3}}{1+(k-1)}+(-1)^{n-3} k(k-1)(k-2) \\
& =(k-1)^{n}+(-1)^{n}(k-1)
\end{aligned}
$$

Therefore, $p_{12,4}$ is equal to $3^{12}+3$, which is 531444.