Problem-Solving StrategyDifficulty 35-953 tagged problems

Monovariants

Monovariants is the habit of finding a quantity that always increases or decreases to prove termination or impossibility. In contest math, that habit turns a crowded setup into a relation the student can test, bound, count, or compute. MathGrit teaches it as a recognizable signal, a deliberate move, and a final translation back to the original question.

Practice this technique Match my level

The Key Result

$$\text{a quantity that changes monotonically (always } \uparrow \text{ or always } \downarrow \text{) and is bounded must eventually stop.}$$

Find a measurement of the configuration that moves in only one direction under every allowed move; since it cannot move forever within its bounds, the process must terminate.

Why It Works

1
Define a numerical quantity (a 'monovariant') attached to the current state of the process.
2
Show that every legal move changes it strictly in one direction — say it strictly decreases by at least a fixed amount.
3
Show it is bounded on that side — e.g. it is a nonnegative integer, so it cannot decrease below $0$.
4
A strictly decreasing sequence of nonnegative integers is finite, so only finitely many moves are possible: the process halts.

Worked Examples

Example 1

On a blackboard are several positive integers. A move erases two numbers $a$ and $b$ and writes their (nonnegative) difference $|a-b|$. Prove the process must eventually stop, and that you can never run it forever.

1
Use the monovariant $S = $ the sum of all numbers on the board (a nonnegative integer).
2
A move replaces $a$ and $b$ by $|a-b|$, changing the sum by $|a-b| - (a+b) = -2\min(a,b) < 0$ when both are positive.
3
So each move strictly decreases the nonnegative integer $S$ by at least $2$.
4
A nonnegative integer cannot strictly decrease forever, so after finitely many moves no two positive numbers remain to combine — the process terminates.

Answer:

The sum is a strictly decreasing nonnegative integer monovariant, so the process always terminates.

Contest level

A row contains the distinct integers in some order. As long as some adjacent pair is out of order — a larger number sitting immediately to the left of a smaller one — you may swap that pair. Prove the process always stops, no matter which swaps you choose.

1
Use the monovariant $I = $ the number of inversions: pairs of positions $i < j$ with $a_i > a_j$. It is a nonnegative integer.
2
Swapping an adjacent out-of-order pair $(\,a_i > a_{i+1}\,)$ fixes exactly that one inverted pair and leaves the relative order of every other pair unchanged.
3
So each legal swap decreases $I$ by exactly $1$, a strict decrease.
4
A nonnegative integer cannot decrease forever; starting from $I_0$ inversions the process halts after exactly $I_0$ swaps, with the row sorted.

Answer:

Inversions form a strictly decreasing nonnegative integer monovariant, so the process always terminates (in exactly the initial number of inversions).

Olympiad / Challenge

Each city in a country is assigned to one of two postal regions, $A$ or $B$. Some pairs of cities are joined by roads. Repeatedly, if any city has more roads to cities in its own region than to cities in the other region, that city switches regions. Prove the switching process must eventually stop.

1
Use the monovariant $M = $ the number of roads joining two cities in different regions (a 'cross' road). It is a nonnegative integer bounded above by the total number of roads.
2
Suppose a city $v$ with $s$ same-region road-neighbors and $d$ other-region neighbors switches; by the rule it switches only when $s > d$.
3
After $v$ switches, its $s$ former same-region roads become cross roads (gaining $s$) and its $d$ former cross roads become same-region (losing $d$); no other road changes type.
4
So $M$ increases by $s - d > 0$ at every move — strictly increasing yet bounded above by the number of roads, so only finitely many switches can occur and the process terminates.

Answer:

The count of cross-region roads is a bounded, strictly increasing integer monovariant, so the process halts.

Going Deeper

A monovariant proves a process terminates or is bounded; a true invariant (a quantity that never changes) instead proves a target state is reachable or impossible — keep the two ideas distinct and reach for the right one.
Monovariants run the engine of olympiad combinatorics and algorithm problems: token-spreading, chip-firing, sorting by swaps, and 'prove this never goes on forever' all hinge on finding the quantity that moves one way.
Pitfall: 'strictly decreasing and bounded below' guarantees termination only for integers (or values forced to drop by at least a fixed amount). A real quantity can decrease forever while staying positive — e.g. $\tfrac12, \tfrac14, \tfrac18, \dots$ — so a continuous monovariant alone does not bound the number of steps.

Spot the Signal

Look for problems where the key step is finding a quantity that always increases or decreases to prove termination or impossibility.
You can describe the hard part as finding a quantity that always increases or decreases to prove termination or impossibility, but a direct attack starts producing clutter.
The problem rewards preserving structure instead of expanding, listing, or guessing too early.

Learn the Move

Start by identify the problem-solving bottleneck that calls for monovariants, then rewrite the givens around it.
Name the relation that makes Monovariants legal before doing computation.
Use the new relation to replace the messiest part of the problem with a cleaner one.
Translate the result back to the quantity the problem actually asks for.

Avoid These Traps

Do not use Monovariants just because the surface looks familiar; verify the required condition first.
Applying Monovariants because it sounds relevant, without checking the trigger first.
Stopping after spotting the technique instead of finishing the calculation or proof.

MathGrit Coach Note

Let monovariants reveal the strategic structure; then compute only what remains.

Try it on:

Practice a contest problem where the key step is finding a quantity that always increases or decreases to prove termination or impossibility.