Coloring Arguments

Color the board so the tiles can't help but disagree with the totals.

The idea

A coloring argument proves that a covering is impossible by counting rather than by search. Reach for one whenever a problem asks whether a region can be tiled by pieces of a rigid shape, or whether a position can be reached by moves with a fixed local footprint. Trying arrangements and failing proves nothing; a proof of impossibility must rule out every arrangement at once, and a counting mismatch does exactly that.

Color the cells of the board so that every allowed piece covers a predictable amount of each color, wherever it lands and however it is turned. A complete tiling by $n$ pieces then covers a total of each color fixed by $n$ alone. Compare that forced total with what the board actually holds: if the two disagree, no tiling exists.

Choosing the pattern is the real work. A useful coloring is one the piece must respect but the board does not. If the counts come out equal, the coloring proves nothing — it is not evidence that a tiling exists — and a different set of marked cells should be tried.

Ways to work on it

• Walkthrough. The mutilated chessboard, and the color count that proves it cannot be tiled.
• Practice. Randomized domino feasibility — let the color counts decide, then construct or refute.
• Hardest. 1 × 4 tiles on an n × n board — pick the right marking, then run the count.

Not sure where to start? Take the ten-question placement test.