An invariant is some property of a system that stays fixed no matter what allowed operation you apply. If you can show that a starting configuration has one value of the invariant, and the desired ending configuration would require a different value, you’ve proven the ending configuration is unreachable — without ever having to search through the space of possible moves.
Parity: the most common invariant
Parity (whether a quantity is even or odd) is by far the most frequently useful invariant on the AMC. Two patterns to watch for:
- An operation that changes a sum by an even amount each time preserves the sum’s parity forever.
- A quantity built from counting swaps, flips, or pairings often has a parity that’s fixed by the structure of the problem, regardless of the specific choices made.
Coloring arguments
A close cousin of parity: color the elements of a configuration (often a grid, like a checkerboard) in two colors, and show that every allowed move affects the two color-counts in a fixed, predictable way. If the target configuration requires a color balance the moves can never produce, it’s impossible.
Worked example
Problem: Standard 8×8 chessboard, with the two opposite corner squares removed (so 62 squares remain). Can this board be tiled exactly by 31 dominoes (each covering 2 adjacent squares)?
Solution: Color the board in the standard checkerboard pattern. There are 32 dark and 32 light squares. The two removed corners are always the same color (opposite corners of a standard chessboard match), so removing them leaves 30 of one color and 32 of the other.
Every domino, no matter where it’s placed, covers exactly one dark and one light square — so any tiling by dominoes must use an equal number of each color. But we have 30 and 32, which are unequal. So the tiling is impossible.
Practice problems
1.Start with the number 1. You may repeatedly add 2. Can you ever reach 100?
2.Five light switches start off. Each move flips exactly 3 of them. Can all five ever be on simultaneously?
3.Can a standard 8×8 chessboard (all 64 squares) be tiled by 32 dominoes? Explain using the coloring argument.
4.A sequence starts at 0. Each step, you either add 3 or subtract 5. Can the sequence ever equal 1?