Learn / Library / Brainteasers
Lamps that never match
A by grid holds lamps, each coloured red, green or blue. Lamps are neighbours if they share an edge. How many colourings of the grid have no pair of neighbouring lamps of the same colour?
Checking an answer needs JavaScript. The hint and the solution open without it.
Hint
Treat the grid as columns of lamps. A column is either of the form "outer lamps equal" or "all different".
Solution
- A valid column of lamps has its middle lamp different from both others, so it has the form ABA (outer lamps equal, of them) or ABC (all different, of them).
- For a column of the form ABA, the next column can be chosen in ways of the form ABA and ways of the form ABC; for a column of the form ABC it is and .
- Let and count colourings of the first columns that end in the form ABA and ABC. Then and for the first column, and each new column gives and .
- The pairs are , , and for to columns, so the total is .
Answer: