Ten lockers are in a row. Each locker is to be painted either blue, red or green. In how many ways can the collection of lockers be painted?

Question

Ten lockers are in a row. The lockers are numbered in order with the positive integers 1 to 10. Each locker is to be painted either blue, red or green subject to the following rules:

• Two lockers numbered $m$ and $n$ are painted different colours whenever $m−n$ is odd.

• It is not required that all 3 colours be used.

In how many ways can the collection of lockers be painted?

---

Attempt:

Notice that the total number of coloring schemes without the rules is $3^{10}$. The total number of coloring schemes where every two side-by-side lockers have different color is $3 \cdot 2^{9}$ (this corresponds to $m-n=1$). The total number of coloring schemes where $m-n = 3$ is $(3 \cdot 2)^{7}$, without considering the others $m-n$. Also for $m-n = 5$, the total number of schemes is $(3 \cdot 2)^{5}$. For $m-n=7$, $(3 \cdot 2)^{3}$. For $m-n=9$, $(3 \cdot 2)$.

How to continue?

Answer 1

We can first divide the lockers into two groups, one for the odd-numbered lockers and the other group for even-numbered lockers. We know that If a colour is used in the one group, then it can't be used in the other group. Then we can divide into $2$ cases.

First case: only two colours is used.

First, we choose two colours, then one of them will be used for the first group and the other will be used for the second group. So the number of ways for this case is $P^3_2=6$.

Second case: all three colours is used.

We can have two colours in a group and one colour for the other group. WLOG, we can assume that red and blue is used for the first group and green for the second group, then multiply the result by $C^3_2\times2=6$, then we will have the answer for this case.

We have $2^5-2=30$ choices for the first group, because there are $2$ choices for each of the $5$ lockers in the first group, but subtracting $2$ for the cases that all of the $5$ lockers in the first group are red or blue. Then, there is only $1$ cases for the second group. That means there are $30\times6=180$ ways for the second case.

So, $180+6=186$ is the answer to the problem.

Answer 2

Note that $m-n$ is odd iff $m$ and $n$ have different parity. So two lockers having different parity must have different colors. So we partition the set of given colors $\{R, G, B\}$ in two non-empty disjoint sets $O$ and $E$. The lockers with odd parity can only be colored with colors in $O$, and lockers with even parity can only be colored with colors in $E$.

Let's suppose $|O|=1$ and $|E|=2$. Number of ways to partition will be $\binom{3}{1}=3$. All odd lockers will have to choose the same color. All even lockers will have to choose one from two available colors. So, number of ways to color in this case is $3 \cdot 1^5 \cdot 2^5 = 96$.

Another case will be $|O|=2$ and $|E|=1$. Proceeding in the same manner, we have our answer as $ \binom{3}{2} \cdot 2^5 \cdot 1^5 = 96$.

Our answer is $96+96=192$.

As mentioned in comments by Culver Kwan, I have double-counted the case when $|O|=|E|=1$. In this case, we can choose $O$ in $3$ ways, and we can choose $E$ from remaining colors in $2$ ways. So, the number of coloring in this case is $3 \cdot 2 \cdot 1^5 \cdot 1^5 = 6$.

We get $192-6=186$ as our answer.