Symmetry, Invariants & Coloring Arguments

Medium3–4 hrsSymmetryInvariantParityColoringImpossibility

Overview

Invariance arguments produce short, elegant proofs of impossibility. The method: find a property of 'legal game states' that is preserved by every legal move. If the goal state violates this property starting from the initial state, the goal is unreachable — no matter how clever you are. The checkerboard coloring is the most famous example; parity arguments are the most versatile.

How to Recognize

→'Prove that X is impossible' — find an invariant
→Tiling or domino problems on a modified board
→Parity arguments: can you reach position B from position A?
→Two-player games where the first player wins by mirroring

Step-by-Step Approach

1.Invariant method: find f(state) that every valid move preserves. If start ≠ goal under f: impossible.
2.Coloring: assign colors to a grid/sequence. Each valid move changes colors in a predictable way.
3.Parity: count something mod 2. If start parity ≠ goal parity: impossible.
4.Symmetry strategy: first player takes the 'center', then mirrors every opponent move.

Key Formulas

01Coloring invariant: every domino covers 1 black + 1 white square → need equal counts

02Parity invariant: a move that changes parity means you alternate between even and odd states

03Symmetry game: player 1 takes center → can mirror every move → player 2 always runs out first

Worked Examples

0Quick Example

8×8 board, two opposite corners removed (same color). 30 black + 32 white squares remain. Domino covers 1+1. Need 31+31. Impossible — coloring proves it in 2 lines.

Problem

An 8×8 chessboard has two diagonally opposite corners removed. Can the remaining 62 squares be tiled by 31 dominoes (1×2 tiles)?

Solution

Color the board black and white alternately. Standard 8×8: 32 black, 32 white.

Two opposite corners: both are the SAME color. (Top-left = black, bottom-right = black on standard coloring.)

After removing both: 30 black, 32 white squares remain.

Each domino covers exactly 1 black + 1 white (dominoes span adjacent squares = opposite colors).

31 dominoes need 31 black + 31 white squares. But we have 30 black and 32 white.

Impossible. The coloring invariant provides a 2-line proof.

Answer

Impossible. Coloring invariant: dominoes always cover equal black and white. Removing two same-color corners creates imbalance (30B vs 32W) → no perfect tiling.

Common Mistakes

!
Trying to construct a solution when the invariant proves it's impossible. Two lines of invariant argument beats hours of failed construction attempts.
!
For parity arguments: carefully count how many elements change per move. 'Each move flips 3' → odd change → parity flips.
!
Symmetry games: the center placement is critical — if the table had no center (e.g., rectangle with even dimensions and no center lattice point), the argument needs rethinking.

Practice Problems

Click "Show Answer" to reveal

Can you tile a 10×10 board (minus two opposite corners) with 1×2 dominoes?

Hint: 10×10 board: how many black and white squares? What color are opposite corners?

An ant starts at corner (0,0) of an n×n grid and wants to reach (n,n). It can only move right (+1,0) or up (0,+1). Color squares like a chessboard. How does the coloring help determine the number of valid paths?

Hint: Every path from (0,0) to (n,n) makes exactly n right moves and n up moves — total 2n moves.

Prove it's impossible to rearrange the numbers 1–9 in a 3×3 grid such that every row, column, and diagonal sums to the same value UNLESS the center is 5.

Hint: The magic constant M = (1+2+...+9)/3. Use the intersection of rows/columns through center.

Back to Study Plan

River Crossings & Constraint Puzzles Strategy Games & Winning Positions