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

combinatoricscontest-mathpermutations

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?

Best Answer

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.

Related Question