Coloring Strategies
Lesson · Intermediate
Combinatorics
Coloring can reveal patterns or invariants in problems involving boards, tilings, and moves.
Checkerboard Coloring
Color the squares alternately black and white, so squares sharing a side have different colors.
A square in row r and column c can be colored according to the parity of
• r + c even → white
• r + c odd → black
Key Idea
After coloring, ask:
How does each allowed move, tile, or operation affect the colors?
Two opposite corner squares are removed from an 8 × 8 chessboard. Can the remaining board be tiled with 31 dominoes, where each domino covers two adjacent squares?
Color the board like a checkerboard.
There are initially 32 black squares and 32 white squares.
Opposite corners of an 8 × 8 board have the same color. Therefore, after removing them, the remaining board has 30 squares of one color and 32 of the other.
Every domino covers exactly one black square and one white square.
Therefore, a tiling would require equal numbers of black and white squares, which is impossible.
A knight starts on a square of a chessboard. Prove that after an odd number of moves, it cannot return to its starting square.
Color the board like a checkerboard.
In the figure shown, a knight can move to any of 8 possible positions in one move: 2 units in one direction and 1 unit in a perpendicular direction.
Every knight move changes the color of the square.
Therefore, after an odd number of moves, the knight is on a square of the opposite color.
Hence, it cannot be back at its starting square.
Is it possible to tile a 10 × 10 board using T-shaped tiles made of four unit squares, as shown below?
Color the 10 × 10 board like a checkerboard. It contains 50 black squares and 50 white squares.
Each T-shaped tile covers either 3 black squares and 1 white square, or 1 black square and 3 white squares.
Since the board has 100 squares, a tiling would use 25 tiles.
Suppose x of the tiles cover 3 black squares and 1 white square. Then the other 25 − x tiles cover 1 black square and 3 white squares.
Counting the black squares gives
so
which is impossible because x must be an integer.