Combinatorics and discrete mathematics

Invariants and monovariants

Quantities that stay fixed, or change monotonically, under the moves of a combinatorial process, used to prove impossibility.

IntuitionWhy some puzzles can never be solved

Remove two opposite corner squares from an $8\times 8$ chessboard, leaving $62$ squares. Can you tile the remaining board with $31$ dominoes of size $2\times 1$ ? Trying by hand fails every time, yet there are millions of ways to place dominoes. Instead of testing cases, look at the colors: each domino always covers $1$ black square and $1$ white square, so $31$ dominoes must cover $31$ black and $31$ white squares. But opposite corners of a chessboard have the same color, leaving $32$ squares of one color and $30$ of the other! The difference $W - B$ is an invariant of domino placement, and it proves impossibility in one line.

Bipartite coloring as an invariant: every edge (domino) connects one vertex from each side, so any perfect matching requires equal counts on both sides.

UndergraduateDefinitions: invariants and monovariants

Definition: Invariant and monovariant of a state system

Consider a combinatorial process with state space $\mathcal{S}$ and allowed transitions $s \to s'$ . A function $I: \mathcal{S} \to X$ is an invariant if $I(s') = I(s)$ for every valid move $s \to s'$ . A real-valued function $M: \mathcal{S} \to \mathbb{R}$ is a monovariant (or potential function) if $M(s') < M(s)$ (strictly decreasing) or $M(s') > M(s)$ (strictly increasing) on every valid move.

I(s_0) = I(s_1) = \cdots = I(s_k) \implies \text{if } I(s_{\mathrm{target}}) \neq I(s_0),\ s_{\mathrm{target}} \text{ is unreachable}

M(s_0) > M(s_1) > M(s_2) > \cdots \ge 0,\quad M(s) \in \mathbb{N} \implies \text{process terminates in } \le M(s_0) \text{ steps}

Common invariant and monovariant templates in competition and research problems
Tool	Typical form	What it proves
Parity invariant	$S \bmod 2$ or $(-1)^{\text{inversions}}$	Target state is unreachable
Modular / algebraic invariant	$\sum a_i \bmod m$ or polynomial evaluation	Final configuration is uniquely determined
Integer monovariant	$M(s) \in \mathbb{N}$ with $M(s') \le M(s) - 1$	Process must halt in $\le M(s_0)$ steps

UndergraduateKey theorems: 15-puzzle parity and monovariant termination

Theorem: Loyd–Johnson 15-puzzle parity invariant

In the $4\times 4$ sliding $15$ -puzzle, let $N(s)$ be the number of tile inversions (pairs $(i,j)$ with $i > j$ such that tile $i$ appears before tile $j$ in row-major snake order) and let $r(s) \in \{1,2,3,4\}$ be the row of the blank square when reading in standard row-major order, or equivalently let $d(s)$ be the Manhattan distance of the blank from the bottom-right corner. Then the parity $(N(s) + r(s)) \bmod 2$ is invariant under every legal slide. In particular, the configuration with tiles $14$ and $15$ swapped is insolvable.

Why is it true?

A horizontal slide leaves the row-major order of the $15$ numbered tiles completely unchanged, while a vertical slide jumps one tile past exactly $3$ other tiles in row-major order (changing the inversion count by $\pm 1$ or $\pm 3$ , always odd) and simultaneously changes the blank's row $r(s)$ by $\pm 1$ .

Proof

Step 1 (horizontal slides). When the blank slides left or right within the same row, no numbered tile changes its position in the row-major listing of the $15$ tiles, and the blank stays in row $r(s)$ . Thus $\Delta N = 0$ and $\Delta r = 0$ , so $N(s) + r(s)$ is unchanged.

Step 2 (vertical slides). When the blank slides up or down, the tile $t$ moving into the blank's old square shifts by $3$ positions in the row-major sequence of the $15$ numbered tiles. Crossing each of those $3$ tiles flips whether $(t, u)$ is an inversion, changing $N(s)$ by $+1$ or $-1$ per tile. The total change is $\Delta N \in \{-3, -1, +1, +3\}$ , which is always odd. At the same time $\Delta r \in \{-1, +1\}$ is also odd, so $\Delta(N + r)$ is even.

Step 3 (swapping 14 and 15). Swapping tiles $14$ and $15$ with the blank fixed at row $r = 4$ changes $N(s)$ by $+1$ (from $0$ to $1$ ) while $\Delta r = 0$ . Hence $(N + r) \bmod 2$ differs between the start state ( $1 + 4 \equiv 1 \pmod 2$ ) and the solved state ( $0 + 4 \equiv 0 \pmod 2$ ), proving no sequence of legal slides can reach the solved state.

Theorem: Well-founded monovariant termination theorem

Suppose every legal move $s \to s'$ of a process decreases an integer-valued function $M: \mathcal{S} \to \mathbb{Z}$ by at least $1$ , i.e. $M(s') \le M(s) - 1$ , and $M(s) \ge 0$ for all states $s \in \mathcal{S}$ . Then starting from any state $s_0$ , the process must terminate in at most $M(s_0)$ steps.

Why is it true?

You cannot step down a staircase of height $M(s_0)$ more than $M(s_0)$ times if each step drops at least one stair and you can never go below the ground floor $0$ .

Proof

**Step 1 (inductive bound after $k$ moves).** Let $s_0 \to s_1 \to s_2 \to \cdots \to s_k$ be any sequence of $k$ valid moves. Applying the hypothesis $M(s_{i}) \le M(s_{i-1}) - 1$ for $i = 1, 2, \dots, k$ and summing telescopes the inequality to $M(s_k) \le M(s_0) - k$ .

**Step 2 (upper bound on $k$ ).** Since $M(s_k) \ge 0$ for every reachable state $s_k \in \mathcal{S}$ , combining the two inequalities gives $0 \le M(s_k) \le M(s_0) - k$ , which rearranges immediately to $k \le M(s_0)$ . Therefore no valid trajectory can have length $k > M(s_0)$ , and the process must terminate in at most $M(s_0)$ steps.

AdvancedReal-World Applications and Worked Examples

In formal verification and software engineering, loop invariants and ranking functions (monovariants) are the standard way proof assistants (Lean, Coq, Dafny) certify that critical algorithms return the right answer and never hang in an infinite loop. In distributed consensus and chip-firing networks, algebraic invariants determine which load-balancing states are reachable.

Example: Erasing two numbers and writing their difference

The numbers $1, 2, 3, \dots, 2026$ are written on a blackboard. Each step, you erase two numbers $a, b$ and write $|a - b|$ in their place, until a single number remains. Can the final number be $0$ ?

Solution

Notice that $|a - b| \equiv a + b \pmod 2$ , because $(a + b) - |a - b| = 2\min(a,b)$ is always even. Thus the parity of the sum of all numbers on the board, $S \bmod 2$ , is an invariant!

Initially the sum is $S_0 = \frac{2026 \times 2027}{2} = 1013 \times 2027$ . Since both $1013$ and $2027$ are odd, $S_0$ is odd ( $S_0 \equiv 1 \pmod 2$ ). After $2025$ steps, the single remaining number must still be congruent to $S_0 \equiv 1 \pmod 2$ , so it is odd and can never be $0$ .

Example: Untangling crossing segments in the plane

Given $n$ red points and $n$ blue points in general position in the plane, we pair them with $n$ straight segments. Whenever two segments $A_1B_1$ and $A_2B_2$ cross, we replace them with $A_1B_2$ and $A_2B_1$ . Prove that this process must terminate in finitely many steps, leaving no crossings.

Solution

Define the potential $L(s) = \sum_{i=1}^n |A_iB_i|$ , the total Euclidean length of the $n$ segments. When $A_1B_1$ and $A_2B_2$ cross at a point $P$ , the triangle inequality in $\triangle A_1 P B_2$ and $\triangle A_2 P B_1$ gives $|A_1B_2| + |A_2B_1| < (|A_1P| + |PB_2|) + (|A_2P| + |PB_1|) = |A_1B_1| + |A_2B_2|$ .

Thus $L(s)$ is a strictly decreasing monovariant on every move! Since there are only $n!$ possible matchings between the $n$ red and $n$ blue points, $L(s)$ can take at most $n!$ distinct values and cannot decrease more than $n! - 1$ times. Hence the process terminates in at most $n! - 1$ steps.

Why is it impossible to tile an $8\times 8$ chessboard missing two opposite corners with $31$ dominoes of size $2\times 1$ ?

Start with five numbers $1, 2, 3, 4, 5$ . Each step you may add $1$ to any two of them. Can all five numbers ever become equal?

An integer-valued monovariant $M(s) \in \mathbb{N}$ starts at $M(s_0) = 42$ and satisfies $M(s') \le M(s) - 3$ on every legal move. What is the maximum number of moves before the process must halt?

When we replace two numbers $a, b$ by $a + b + ab$ , which algebraic quantity stays invariant across the whole list?

References

Arthur Engel (1998). Problem-Solving Strategies · DOI:10.1007/b97682
Jessica Striker (2017). Dynamical Algebraic Combinatorics: Promotion, Rowmotion, and Resonance · DOI:10.1090/noti1539