Technique Encyclopedia
Monovariants
What it is
A monovariant is a quantity that moves in one direction only — always increasing, or always decreasing — with every step of a process. Since it's bounded (it can't decrease forever below some floor, or increase forever past some ceiling), the process itself must eventually stop.
Signals that suggest using it
- A process or game involves repeated moves that could, in principle, go on forever.
- "Show that this process must terminate" or "prove the game cannot continue indefinitely."
- A quantity that seems to only ever grow or only ever shrink with each step.
When it's effective
Monovariants are the standard tool for termination proofs — showing a repeated process can't loop forever — and for bounding how many steps a process can possibly take.
When it's not effective
If the quantity you've picked can both increase and decrease depending on which move is chosen, it isn't a monovariant at all — the argument breaks down and a different quantity (or a different technique) is needed.
Simple example
Problem
A board holds several positive integers. Each move picks two numbers a
Solution
Each move replaces two numbers summing to a+b with a single number b-a, so the total sum of all numbers on the board strictly decreases by 2a — a positive amount — every move. Since the sum is a positive integer that strictly decreases, it cannot decrease forever, so the process must terminate.
AMC-style example
Problem
A pile starts with 20 stones. Two players alternate removing 1, 2, or 3 stones from the pile until it is empty. What is the maximum possible number of moves in the game?
Solution
The pile size is a monovariant — it strictly decreases by at least 1 every move, and the game ends when it hits 0. To maximize the number of moves, every move should remove as few stones as possible: 1 stone per move. That gives 20 moves, the maximum possible.