CombinatoricsIntermediate Level

⏱ 15 min lessonAugust 2026

The Invariance Principle

Parity, Modular Residues, Colorings & Monovariants

// Theory

Theory & Core Principles

Introduction & Core Concept

In many competition problems, you are presented with a system that changes according to specified rules (e.g. numbers written on a blackboard replaced by their difference, tokens moved on a grid, or chameleons changing colors). The question often asks whether a certain state can ever be reached.

Directly tracking all possible sequences of moves rapidly leads to exponential growth. The Invariance Principle instructs us to ignore the transient states and look for a property or quantity $I(S)$ of the system state $S$ that remains constant under every valid operation:

$$I(S_{\text{initial}}) = I(S_{\text{next}}) = I(S_{\text{final}})$$

If the desired final state $S_{\text{target}}$ has $I(S_{\text{target}}) \neq I(S_{\text{initial}})$, then the target state is impossible to reach!

---

Standard Invariant Taxonomies

1
Parity Invariants: Quantities whose oddness/evenness does not change under valid moves. (e.g. Replacing $a, b$ with $|a-b|$ preserves the parity of the sum $a+b$).
2
Modular Residue Invariants: Quantities that remain invariant modulo $m$. (e.g. Modulo $3$ invariants in chameleon color-changing problems).
3
Grid & Coloring Invariants: Assigning colors or algebraic values ($1, -1, i$) to grid cells to show certain tilings or configurations are impossible.
4
Monovariants: Quantities that strictly increase or decrease with each step, proving that processes must terminate or cannot loop.

---

Standard 4-Step Execution Workflow

1
Observe: Identify what changes and what stays the same after one step of the process.
2
Define: Define a mathematical function $I(S)$ on the state (e.g. sum, product, parity, count modulo $k$).
3
Verify: Verify that $I(S_{\text{after}}) = I(S_{\text{before}})$ for every allowed move.
4
Conclude: Compare $I(S_{\text{initial}})$ with $I(S_{\text{target}})$. If they differ, the target state is impossible.

// Worked Examples

Worked Examples

Step-by-step solutions showing how to apply the technique.

Worked Example 1: The Defective Chessboard

// Problem

Consider a standard $8 \times 8$ chessboard. Two diagonally opposite corner squares are removed. Can the remaining $62$ squares be completely covered with $31$ non-overlapping $1 \times 2$ dominoes?

Key Idea

Each domino covers exactly one black square and one white square on the chessboard.

// Solution

1
Initial State Analysis: A standard $8 \times 8$ chessboard contains 32 white squares and 32 black squares.
2
Modification: Diagonally opposite corners on a chessboard always have the same color. Suppose we remove two white corners. The remaining board has 30 white squares and 32 black squares.
3
The Invariant: Every $1 \times 2$ domino placed on the board covers exactly 1 white square and 1 black square. Thus, 31 dominoes will always cover exactly 31 white squares and 31 black squares.
4
Conclusion: Since $30 \neq 32$, it is impossible to tile the defective board with 31 dominoes.

Worked Example 2: The Blackboard Numbers Game

// Problem

The numbers $1, 2, 3, \dots, 2026$ are written on a blackboard. In one step, you choose any two numbers $a$ and $b$, erase them, and write $|a - b|$ in their place. This step is repeated until only one number remains. Can the final number be $0$?

Key Idea

Examine how the sum of all numbers on the board changes modulo 2 after each step.

// Solution

1
Track the Sum: Let $S$ be the sum of all numbers currently on the blackboard.
2
Effect of a Move: When $a$ and $b$ are replaced by $|a - b|$, the new sum becomes:

$$S_{\text{new}} = S - a - b + |a - b|$$

Notice that $|a - b| \equiv a + b \pmod{2}$ because $|a - b|$ and $a + b$ always have the exact same parity.

3
Parity Invariant: Therefore:

$$S_{\text{new}} \equiv S - a - b + (a + b) = S \pmod{2}$$

The parity of the sum of numbers on the board is invariant!

4
Initial Sum Calculation:

$$S_{\text{initial}} = 1 + 2 + \dots + 2026 = \frac{2026 \times 2027}{2} = 1013 \times 2027$$

Since $1013$ and $2027$ are both odd, $S_{\text{initial}}$ is odd.

5
Conclusion: The final remaining single number must have the same parity as $S_{\text{initial}}$, which is odd. Since $0$ is even, the final number can never be 0.

Worked Example 3: Circle of Coin Flips

// Problem

$10$ coins are arranged in a circle, all showing Heads. In one move, you may flip any $4$ consecutive coins. Can you reach a state where all $10$ coins show Tails?

Key Idea

Group coins into odd and even indexed positions around the circle.

// Solution

1
Parity at Odd/Even Positions: Assign indices $1, 2, \dots, 10$ to the coins in order.

1
Effect of a Flip: Any 4 consecutive coins contain exactly 2 odd-indexed coins and 2 even-indexed coins!

1
The Invariant: Flipping 2 odd-indexed coins changes the number of Tails at odd positions $T_{\text{odd}}$ by $+2, 0,$ or $-2$.

Thus, $T_{\text{odd}} \pmod 2$ is strictly invariant!

1
Initial vs Target:

■
Initial State: All coins Heads $\implies T_{\text{odd}} = 0$ (even).
■
Target State: All 10 coins Tails $\implies T_{\text{odd}} = 5$ (odd).

5
Conclusion: Since $0 \not\equiv 5 \pmod 2$, it is impossible to reach all Tails!

Worked Example 4: The Chameleon Island

// Problem

An island has 13 red, 15 green, and 17 blue chameleons. Whenever two chameleons of different colors meet, they both change into the third color. Can all 45 chameleons ever become the same color?

Key Idea

The difference between the counts of any two colors modulo 3 remains constant after every meeting.

// Solution

1
Initial State Analysis: The chameleon counts are $R = 13$, $G = 15$, and $B = 17$. The pairwise differences are $R - G = -2 \equiv 1 \pmod 3$, $G - B = -2 \equiv 1 \pmod 3$, and $B - R = 4 \equiv 1 \pmod 3$.
1
The Invariant: When two chameleons of different colors meet (e.g., Red and Green produce two Blue), the counts change by $\Delta R = -1$, $\Delta G = -1$, and $\Delta B = +2$. The change in difference between any two colors is always $0$ or $\pm 3$, meaning $(R - G) \pmod 3$, $(G - B) \pmod 3$, and $(B - R) \pmod 3$ remain invariant.
1
Target State Analysis: To make all 45 chameleons the same color, two colors must simultaneously equal 0 (e.g., $45$ Red, $0$ Green, $0$ Blue). This target state requires the difference between the two zero-count groups to be $0 - 0 = 0 \equiv 0 \pmod 3$.
1
Conclusion: Since the initial differences are all congruent to $1 \pmod 3$, the system can never reach a state where any pairwise difference is congruent to $0 \pmod 3$. Therefore, it is impossible for all chameleons to become the same color.

// Practice

Practice Problems

Try solving these problems on your own before checking the hints or solution.

Practice Challenge 1: The Chameleons of Island Alpha

Intermediate Level

// Problem

On an island there are $13$ Red, $15$ Green, and $17$ Blue chameleons. Whenever two chameleons of different colors meet, they both change their color to the third color. Can all chameleons on the island eventually become the same color?

// Hints

Practice Challenge 2: Grid Token Invariant

Advanced Level

// Problem

A token is placed at $(0,0)$ of an infinite grid. In one move, a token at $(x,y)$ splits into two tokens at $(x+1, y)$ and $(x, y+1)$. Can you clear the region $x + y \le 1$ of all tokens?

// Hints

Practice Challenge 2: The Blackboard Numbers

Intermediate Level

// Problem

The numbers $1, 2, 3, \dots, 2026$ are written on a blackboard. At each step, you pick any two numbers $a$ and $b$, erase them, and write the value $|a - b|$ in their place. This operation is repeated until only a single number remains. Can the final number be $0$?

// Hints