2
$\begingroup$

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?

I had thought that if you choose a specific seat to start with, say, $a_1$, and WLOG it is red. Then there are two cases: $a_2$ and $a_6$ (chairs adjacent to $a_1$) are both the same colour or are two different colours.

Case 1: $a_2$ is blue and $a_6$ is green. Then if both $a_3$ and $a_5$ are red, $a_4$ has two choices: green or blue. So from this example there are $3 \cdot 2 \cdot 2 = 12$ possible ways.

Case 2: Again, $a_2$ is blue and $a_6$ is green. But if $a_3$ is green and $a_5$ is blue, then $a_4$ must be red. There are $3 \cdot 2$ choices.

Case 3: As before, $a_2$ is blue and $a_6$ is green. But if $a_3$ is red and $a_5$ is blue, then $a_4$ must be green. $3 \cdot 2 \cdot 2 = 12$

So in total I had $12 + 6 + 12 = 30$ ways but the answer was $66$. I do think my reasoning might have some flaws here, but I need help.

$\endgroup$
  • $\begingroup$ are the seats numbered? Is it the same coloring if I rotate the whole situation? $\endgroup$ – Nathanael Skrepek May 26 '18 at 10:08
  • 1
    $\begingroup$ You're not considered the second case (a2 and a6 are both the same colour). $\endgroup$ – Vladislav Alexeev May 26 '18 at 10:35
0
$\begingroup$

I seems that you are right. At least the answer is correct. I can offer a different approach. I assume that the seats are numbered i.e. a rotated coloring is a different coloring.

Let $c_n$ be the number of valid colorings for $n$ seats and $a_i$ denotes the color of the $i$-th seat. I will make a recursive formula by removing seats. The neighbors of $a_n$ are $a_{n-1}$ and $a_1$.

  1. case: If $a_1 \neq a_{n-1}$, then I can remove $a_6$ and obtain a valid coloring for $n-1$ seats.
  2. case: If $a_1 = a_{n-1}$, then $a_{n-2} \neq a_{n-1} = a_1$. So I can remove $a_n$ and $a_{n-1}$ and obtain a valid coloring for $n-2$ seats.

Since in the second case there are two options for $a_n$ we have the following recursion $$ c_n = c_{n-1} + 2 c_{n-2} $$ There are ways of getting explicit expressions for this, but since we are only interested in $c_6$ we can solve this by follow the recursion. It is easy to check that $c_1 = 0$ and $c_2 = 6$. If you regard $c_1$ as a pathological case, then you can even easily check that $c_3 = 6$. Hence, \begin{align} c_4 &= c_3 + 2 c_2 = 3\cdot 6 = 18, \\ c_5 &= c_4 + 2 c_3 = 5\cdot 6 = 30, \\ c_6 &= c_5 + 2 c_4 = 11\cdot 6 = 66 \end{align}

$\endgroup$
  • $\begingroup$ — sorry if this should be obvious, but I'm not quite sure why $c_1 = 0$ because if there's one seat, then can't we colour it in 3 ways: red, blue, green? But otherwise it makes sense, so thank you :) $\endgroup$ – jjhh May 26 '18 at 12:12
  • $\begingroup$ but the neighbor of $a_1$ is $a_1$ again so you cannot fulfill your condition. However, this is the pathological case, just start with $c_2$ and $c_3$. $\endgroup$ – Nathanael Skrepek May 26 '18 at 12:45
  • $\begingroup$ oh yeah, right—that makes sense. $\endgroup$ – jjhh May 26 '18 at 13:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.