Problem #67 MEDIUM
The Colour-Blind Painter
Google Amazon Combinatorics Graph Theory
Problem Statement
A painter is given a 1×n strip of tiles. She must colour each tile either red or blue such that no two adjacent tiles share the same colour. How many distinct valid colourings exist for a strip of n tiles? Now suppose a third colour — green — is also allowed, but the same adjacency rule applies: no two neighbouring tiles can share the same colour. How many valid colourings exist for n tiles with 3 colours?
Answer & Quick Explanation
Think you've got it? Click below to check your answer.
With 2 colours: exactly 2 valid colourings. With 3 colours: 3 × 2^(n-1) valid colourings. General formula for k colours and n tiles: k × (k-1)^(n-1). This is the chromatic polynomial of the path graph P_n.
Detailed Editorial Solution
Want to see the step-by-step breakdown? Click below to reveal the editorial.
Model each tile as a node in a sequence. The constraint is that adjacent nodes must differ in colour. This is equivalent to counting proper colourings of a path graph P_n with k colours.
Step 1: With 2 colours (Red, Blue): Tile 1 has 2 options (R or B). Tile 2 must differ from tile 1 → 1 option. Tile 3 must differ from tile 2 → 1 option. Each tile after the first is forced. Total = 2 × 1^(n-1) = 2.
Step 2: With 3 colours (Red, Blue, Green): Tile 1 has 3 options. Tile 2 must differ from tile 1 → 2 options (any colour except tile 1's). Tile 3 must differ from tile 2 → 2 options. Pattern continues.
Step 3: Total with 3 colours = 3 × 2 × 2 × ... × 2 (n-1 twos) = 3 × 2^(n-1).
Step 4: General formula with k colours: k × (k-1)^(n-1). This is the chromatic polynomial of a path graph P_n evaluated at k.
Step 5: Verify for n=3, k=3: 3 × 2^2 = 12. Manual check: RBR, RBG, RGB, RGR, RGR, RGR... list all: first tile R → tile 2 is B or G (2 options) → tile 3 differs from tile 2 (2 options each) → 1 × 2 × 2 = 4 per first colour × 3 colours = 12. Confirmed.
Step 6: The chromatic polynomial generalises to any graph: for a path of n nodes with k colours it is always k(k-1)^(n-1).
Key Insight:
Once the first tile is chosen, every subsequent tile has exactly (k-1) choices — any colour except the previous tile's. This multiplicative structure makes the formula immediate. The chromatic polynomial of a path graph is one of the simplest and most elegant results in graph colouring theory.