16. Fnargs are either red or blue and have 2,3 or 4 heads. A group of six Fnargs consisting of one of each possible form is made to line up such that no immediate neighbours are the same colour nor have the same number of heads.
How many ways are there of lining them up from left to right?
A 12
B 24
С 60
D 120
E 720
Solution
A
We let R2, R3, R4 be red Fnargs with 2, 3 and 4 heads, respectively, and B2, B3, B4 be blue Fnargs with 2,3 and 4 heads, respectively. We need to count the number of ways of lining up R2, R3, R4, B2, B3, B4 so that no two Fnargs that are next to each other have the same colour or the same number of heads.

Suppose that a row of these six Fnargs begins with R2 at the left hand end. The second Fnarg in the row must be blue and have 3 or 4 heads. So the row either begins R2, B3 or R2, B4.

If the row begins R2, B3 the third Fnarg must be red and cannot have 3 heads. Since R2 is already in the line up, the third Fnarg must be R4. The fourth Fnarg must be blue and cannot have 4 heads. Since B3 is already in the row, this fourth Fnarg must be B2. This leaves just R3 and B4 to be placed. So, as the colours must alternate, the fifth and sixth Fnargs in the row must be R3 and B4 in this order from left to right. Hence the line up must be
R2, B3, R4, B2, R3, B4.

A similar argument shows that if the row begins R2, B4, then the line up must be as above but with 3 and 4 interchanged, that is,
R2, B4, R3, B2, R4, B3.

So there are just two ways to complete a row that begins with R2.
A similar argument shows that whichever Fnarg begins a row, there are just two ways to complete the row.

Since the row may begin with any of the six Fnargs, the total number of ways to line them up is $6 \times 2=12$.

FOR INVESTIGATION
16.1 As a result of a genetic modification there are now Fnargs with 2, 3, 4 or 5 heads, but still only red or blue. In how many ways can we line up eight Fnargs consisting of one of each possible form so that two adjacent Fnargs have neither the same colour nor the same number of heads?
16.2 As a result of a further genetic modification there are now red, blue and green Fnargs, each with $2,3,4$ or 5 heads. In how many ways can we line up twelve Fnargs consisting of one of each possible form so that two adjacent Fnargs have neither the same colour nor the same number of heads?