Finding What Doesn't Change: The Invariant Technique

Quick Revisit

• USE WHEN: process applies operations until termination — find a quantity that never changes (or only decreases)
• INVARIANT: find I(state) preserved by every legal move; target reachable only if I(target) = I(start)
• TIME: O(1) to check invariant after setup | SPACE: O(1)
• CLASSIC BUG: invariant is necessary but not sufficient — parity matches yet state is still unreachable
• PRACTICE: 08-ladder-mixed

The problem says "apply operations until impossible." You simulate for small inputs and notice: the parity of some quantity never changes. Congratulations -- you found an invariant.

Difficulty: [Intermediate-Advanced]CF Rating Range: 1500-2200 Prerequisites: Game Theory & Nim, Constructive Algorithms

Contents

• What Is an Invariant?
• Types of Invariants
• Five Worked Examples
• How to Find the Invariant
• Practice Problems

---

What Is an Invariant?

An invariant is a quantity that remains unchanged no matter which allowed operation you perform. If you can prove that a quantity $I$ satisfies $I({\text{state}}_{\text{before}})=I({\text{state}}_{\text{after}})$ for every legal move, then $I$ is fixed forever. Any state with a different value of $I$ is unreachable.

This is absurdly powerful. Instead of searching through an exponential state space, you compute a single number and check whether the target is consistent with it.

Types of Invariants

Parity invariants

The simplest class. An operation changes two things by 1 each, so their sum stays even/odd. XOR of an array, sum mod 2, checkerboard coloring on a grid -- all parity arguments.

Litmus test: if every operation changes a quantity by an even amount, its parity is fixed. Check parity first; it's free and catches many "impossible" cases.

Monovariants

Not strictly invariants -- these quantities change, but only in one direction. A monovariant strictly increases or strictly decreases with each operation. It doesn't tell you what the final state is, but it guarantees the process terminates -- and often bounds the number of steps.

Example: if every operation reduces the total number of inversions in a permutation, the process must stop within $(\genfrac{}{}{0ex}{}{n}{2})$ steps.

Sum and product invariants

Operations that redistribute without changing the total. "Remove $a$ from pile A and add $a$ to pile B" preserves the sum. "Replace $(a,b)$ with $(ab,1)$" preserves the product.

Potential functions

A generalization of monovariants used in amortized analysis. Define a "potential" $\mathrm{\Phi }(\text{state})$ that measures how far the system is from equilibrium. Each operation decreases $\mathrm{\Phi }$ by at least some $\delta >0$, bounding the total number of operations by ${\mathrm{\Phi }}_0/\delta$.

Five Worked Examples

1. Sorting with Adjacent Swaps: Inversion Parity

Problem: Given a permutation, can you sort it using adjacent swaps if you're only allowed an even number of swaps?

Invariant: Each adjacent swap changes the inversion count by exactly $\pm 1$. Sorting requires exactly $\text{inv}(P)$ swaps (where $\text{inv}$ counts inversions). So the answer is "yes" if and only if $\text{inv}(P)\equiv 0(\mathrm{mod}2)$.

Permutation:  3 1 2   ->  inversions: (3,1), (3,2)  ->  inv = 2 (even)
              OK Can sort with an even number of adjacent swaps.

Permutation:  2 1 3   ->  inversions: (2,1)          ->  inv = 1 (odd)
              X Cannot sort with an even number of swaps.

This extends to the 15-puzzle: the puzzle is solvable if and only if the inversion count plus the row of the blank tile has the right parity.

2. Coloring a Grid: Checkerboard Parity

Problem: A grid is initially black/white in a checkerboard pattern. The operation: pick two adjacent cells (sharing an edge) and toggle both colors. Can you reach an all-white grid?

Invariant: Color the cells like a checkerboard with weights $+1$ on white squares, $-1$ on black squares. Define $S$ = sum of weights of cells currently colored white. A toggle on adjacent cells flips one white and one black, so $S$ changes by $-1+1=0$ — invariant.

The starting and target configurations differ in $S$, so the target is unreachable. This is the standard 2-coloring trick: an operation that touches one cell of each color preserves any quantity that sums positive on one color and negative on the other.

3. Replace (a, b) with (a+b, a-b): Sum of Squares

Problem: You have a pair of integers $(a,b)$. Repeatedly apply the operation $(a,b)\to (a+b,a-b)$. Can you reach $(c,d)$ from $(a,b)$?

Invariant: Compute $a^2+b^2$ before and after:

$$(a+b{)}^2+(a-b{)}^2=2a^2+2b^2$$

So $a^2+b^2$ doubles with each operation. After $k$ operations: $a_k^2+b_k^2=2^k(a_0^2+b_0^2)$.

To reach $(c,d)$ from $(a,b)$, you need $c^2+d^2=2^k(a^2+b^2)$ for some non-negative integer $k$. This is an extremely restrictive condition -- most targets are unreachable.

4. Nim-Value as Invariant Under Optimal Play

Problem: Two players alternately remove stones from piles. The player who takes the last stone wins. Which player has a winning strategy?

Invariant: The XOR (nim-sum) of all pile sizes. A position is losing if and only if the nim-sum is 0. Every move from a zero-nim-sum position produces a nonzero nim-sum, and from any nonzero-nim-sum position, there exists a move to reach nim-sum 0.

This isn't just a trick for Nim -- the Sprague-Grundy theorem extends it to any impartial game. See Game Theory & Nim.

5. Proving Termination via Monovariant

Problem: Given an array, repeatedly find any pair $a_i>a_j$ where $i<j$ and swap them. Prove that the process terminates.

Monovariant: The number of inversions, $\text{inv}(A)=|\{(i,j):i<j,a_i>a_j\}|$. Each swap reduces the inversion count by at least 1 (and possibly more, but never increases it). Since $\text{inv}(A)\ge 0$, the process terminates in at most $(\genfrac{}{}{0ex}{}{n}{2})$ steps.

This is exactly why bubble sort terminates. The monovariant also gives the worst-case bound: $O(n^2)$ swaps for a reverse-sorted array.

How to Find the Invariant

When a problem involves repeated operations and asks "is state $X$ reachable?" or "prove the process terminates," try this checklist:

1. Simulate small cases. Run the operations by hand for $n=3,4,5$. Write down the state after each step.
2. Compute everything. For each state, record: sum, product, XOR, parity of sum, max, min, number of components, number of inversions, sum of squares, GCD of all elements.
3. Look for constancy. Which quantities stayed the same across all transitions? That's your candidate invariant.
4. Prove it. Show algebraically that the operation preserves the quantity. This is usually a one-line calculation.
5. Apply it. If the initial and target states have different invariant values, the answer is "impossible." If the invariant matches, you may need a constructive argument to show reachability (the invariant alone proves necessary, not always sufficient).

For monovariants: instead of looking for constancy, look for monotonicity. Which quantities always increased (or always decreased)?

Necessary, but not sufficient — when parity matches and the target is still unreachable

The trap of weak invariants: matching one invariant proves nothing on its own. A concrete example.

Setup. Five tokens on a path of vertices $1$–$5$, initially at vertex $1$. The operation: pick a token and move it from its current vertex to an adjacent vertex. We want to reach the configuration "all five tokens at vertex $5$" using exactly $20$ moves.

A naïve invariant. "Total displacement parity": each move changes one token's position by $\pm 1$, so the sum of token positions mod 2 flips with every move. Start: $5\cdot 1=5$ (odd). After 20 moves: parity flipped 20 times, returns to odd. Target: $5\cdot 5=25$ (odd). Parity matches.

But the target is unreachable in exactly 20 moves. Each token must travel distance 4, total 20 moves minimum. So 20 moves is achievable only if every move strictly advances a token. There is no slack — but there's also no actual obstruction, so this case is reachable.

Now flip the question to 21 moves. Parity check: 5 (odd) → 21 flips → even. Target: 25 (odd). Parity mismatch ⇒ unreachable. Good.

How about 22 moves? Parity: 5 → 22 flips → odd. Target: 25 odd. Matches. Yet 22 moves is also unreachable, because each "wasted" pair of moves (forward then back) consumes two moves and undoes itself, but you only have 2 spare moves — and you need an even number of each token's moves to be cancellable, not just the global sum. So the displacement-parity invariant is necessary but not sufficient: it lets through 22-move configurations that a per-token analysis would reject.

The lesson generalizes: when an invariant only tracks an aggregate quantity, it misses obstructions hiding in the per-component structure. Before declaring a target reachable because the invariant matches, construct an explicit sequence of moves or find a stronger invariant that touches the missing structure.

                       compute I(state)
Problem: "is target    ─────────────────►  I(start) != I(target)?
  reachable?"                                   │
                                           yes ─┘─► IMPOSSIBLE (proven)
                                                │
                                           no  ─┘─► need a constructive proof,
                                                    OR a finer invariant

Practice Problems

Problem	Invariant Type	Source
CF 1147C -- Thanos Nim	Sum monovariant; minimum element analysis	CF
CF 1451D -- Circle Game	Geometric invariant; distance to target	CF
CF 1365D -- Solve The Maze	Parity / reachability invariant on grid	CF
CF 1505C -- Fibonacci Words	Character count invariant	CF
CF 1458A -- Row GCD	GCD invariant under addition	CF

---

See also: Game Theory & Nim for the Sprague-Grundy framework, and Constructive Algorithms for problems where you must construct a solution once you've proven it exists.