23. Six seats are arranged in a circular table. Each seat is to be painted in red, blue or green such that any two adjacent seats have different colours. How many ways are there to paint the seats?
23. Answer: 66 .
Let $n \geq 2$ be an integer, and let $S_{n}$ denote the number of ways to paint $n$ seats $a_{1}, \ldots, a_{n}$ as described, but with $a_{1}$ peinted red. Consider $S_{n+2}$ where $n \geq 2$.
Case 1: $a_{3}$ is painted red. Then there are 2 choices for $a_{2}$. Thus, the total number of ways for this case is $2 S_{n}$.
Case 2: $a_{3}$ is not painted red. Since the colour of $a_{2}$ is uniquely determined by the colour of $a_{3}$, this is equivalent to the case when there are $(n+1)$ seats. The total number of ways for this case is $S_{n+1}$.

We conclude that $S_{n+2}=S_{n+1}+2 S_{n}$. It is clear that $S_{2}=S_{3}=2$. Then $S_{4}=6, S_{5}=10$ and $S_{6}=22$. So the required number of ways is $3 \times 22=66$.