An invariant is a quantity or property that never changes as a process runs, no matter what moves or steps are taken. A monovariant is a quantity that changes in only one direction — it can only increase, or only decrease, but never reverses. Both are powerful proof tools. If you can show an invariant has a certain value at the start and a different value at the proposed end, you have proven the end state is unreachable. If you can show a monovariant decreases with each step and is bounded below, you have proven the process must eventually stop. These concepts turn many "is it possible?" questions into clean proofs.
Start with the classic checkerboard puzzle: remove two opposite corners of an 8×8 board. Can you tile the remaining 62 squares with dominoes? Each domino covers one black and one white square, so the number of black minus white squares covered is always 0 — that is the invariant. But two opposite corners have the same color, so the remaining board has 30 of one color and 32 of the other. The invariant (equal coverage) cannot match the board (unequal colors), so tiling is impossible. For monovariants, use the Euclidean algorithm: at each step, the remainder decreases, and it cannot go below 0, so it must terminate.
Some of the most satisfying proofs in mathematics answer the question "is this possible?" with a definitive no — and they do it by finding a quantity that constrains what can happen. That quantity is an invariant if it never changes, or a monovariant if it only moves in one direction.
Consider the classic mutilated checkerboard problem. An 8×8 checkerboard has 32 black squares and 32 white squares. Remove two opposite corners — both the same color, say both white. You are left with 30 white and 32 black squares. Can you tile the remaining 62 squares with 31 dominoes, each covering exactly two adjacent squares? The key observation: every domino, no matter how you place it, covers exactly one black square and one white square. So the number of black squares covered always equals the number of white squares covered. This is the invariant. But to tile the board, you would need to cover 32 black and 30 white — unequal numbers. The invariant makes this impossible. No amount of cleverness can overcome a mathematical invariant.
Monovariants solve a different type of problem: they prove that processes must terminate. The Euclidean algorithm for finding the greatest common divisor repeatedly replaces the larger number with the remainder when dividing. At each step, the remainder is smaller than the divisor, so the sequence of remainders is a monovariant — it strictly decreases. Since remainders are non-negative integers, the sequence cannot decrease forever. It must eventually reach 0, at which point the algorithm stops and the last non-zero remainder is the GCD.
Finding the right invariant or monovariant is the creative challenge. There is no algorithm for this — it requires insight about the problem's structure. Common places to look: parity (is a count even or odd?), sums, products, colorings, modular arithmetic (what is the quantity mod 2? mod 3?). The checkerboard problem uses a coloring invariant. The coin-splitting problem uses an algebraic invariant. The Euclidean algorithm uses a size monovariant. Each problem has its own natural invariant, and part of the art of mathematics is learning to see it.
The general principle is this: if you want to prove something is impossible, find a quantity that the rules of the problem prevent from changing (or only allow to change in one direction), and show that the start and end states disagree on that quantity. If the invariant says "this property stays the same forever" and the target state has a different value of that property, the target is unreachable — not because you tried and failed, but because the mathematics forbids it.
No topics depend on this one yet.