A rectangular wall is partitioned into 5 rectangular parts as shown in the following diagram. If you have three different colours to paint the wall and if no two adjacent parts are to be painted with the same colour, in how many different ways can one paint the wall?
[Note: This question refers to a diagram. As per the official solution, the diagram shows a rectangular wall divided into five rectangular parts: top-left (TL), bottom-left (BL), top-middle (TM), bottom-middle (BM), and a single full-height part on the right (R). Parts sharing a boundary (and so requiring different colours) are: TL–BL, TL–TM, BL–BM, TM–BM, TM–R, and BM–R.]
- A16
- B17
- C18
- D19
Explanation
With the five regions TL, BL, TM, BM and R and the given adjacencies (TL–BL, TL–TM, BL–BM, TM–BM, TM–R, BM–R), a direct enumeration of all 3-colourings with no two adjacent regions sharing a colour gives exactly 18 valid colourings. For instance, fixing TM's colour (3 choices) and counting consistent colourings of the remaining chain and the right region yields 6 per choice. Hence option C (18) is correct.