The Central Idea
Suppose a system moves through states
\[ S_0,S_1,S_2,\ldots \]according to some allowed operation.
An invariant is a quantity or property that remains unchanged under every allowed move.
A monovariant is a quantity that always moves in one direction, such as always increasing or always decreasing.
These ideas reduce a complicated process to something easier to track.
What Is an Invariant?
Let \(I(S)\) be a quantity associated with a state \(S\).
If every legal move
\[ S\longrightarrow S' \]satisfies
\[ I(S')=I(S), \]then \(I\) is an invariant.
Thus,
\[ \boxed{I(S_0)=I(S_1)=I(S_2)=\cdots.} \]What Is a Monovariant?
Let \(M(S)\) be a quantity associated with a state.
If every legal move satisfies either
\[ M(S')then \(M\) is a strict monovariant.
A non-strict monovariant may satisfy
\[ M(S')\le M(S) \]or
\[ M(S')\ge M(S). \]Invariant versus Monovariant
An invariant remains constant:
\[ \boxed{\text{same value after every move}.} \]A monovariant changes predictably in one direction:
\[ \boxed{\text{never reverses direction}.} \]Invariants are especially useful for proving impossibility.
Monovariants are especially useful for proving progress or termination.
Why These Methods Matter
A process may have exponentially many or even infinitely many possible move sequences.
Tracking them one at a time may be impossible.
An invariant or monovariant can summarize all legal moves at once.
The proof shifts from
“What happens in every possible sequence?”
to
“What quantity does every legal move preserve or move predictably?”
The Basic Invariant Strategy
- Describe the initial state.
- Identify a candidate quantity or property.
- Prove that every legal move preserves it.
- Compute or identify its value in the initial state.
- Compare that value with the proposed target state.
- If the target has a different invariant value, conclude that the target is unreachable.
The Basic Monovariant Strategy
- Define a quantity associated with each state.
- Prove that every legal move changes it in one direction.
- Identify a lower or upper bound when relevant.
- Use the directional change to prove progress, termination, or impossibility of cycling.
Parity as an Invariant
Parity is one of the most common invariants.
A quantity may change numerically while preserving whether it is even or odd.
For example, adding \(2\) changes an integer \(n\) to
\[ n+2, \]but
\[ n\equiv n+2\pmod2. \]Therefore parity is preserved.
Example: Repeatedly Adding or Subtracting 2
Start with the integer
\[ 7. \]At each move, add \(2\) or subtract \(2\).
Can the process ever reach \(10\)?
Every move preserves parity because
\[ n\pm2\equiv n\pmod2. \]The starting number \(7\) is odd, so every reachable number is odd.
But \(10\) is even.
Therefore,
\[ \boxed{10\text{ is unreachable}.} \]Modular Arithmetic Produces Invariants
More generally, if every move changes a quantity by a multiple of \(m\), then its residue modulo \(m\) is invariant.
If
\[ x'\;=\;x+km \]for some integer \(k\), then
\[ x'\equiv x\pmod m. \]Thus modular arithmetic is a systematic source of invariants.
Example: Moves of Size 6
Start at
\[ 5. \]Every move adds or subtracts \(6\).
Every reachable number satisfies
\[ n\equiv5\pmod6. \]Since
\[ 20\equiv2\pmod6, \]the value \(20\) cannot be reached.
Coloring as an Invariant
In geometric and board problems, a coloring can encode an invariant.
The colors themselves are not necessarily the invariant.
What matters is a quantity derived from the coloring, such as:
- the difference between counts of two colors;
- the parity of a color count;
- a weighted color sum.
The Checkerboard Coloring
Color a standard \(8\times8\) checkerboard alternately black and white.
The board contains
\[ 32 \]black squares and
\[ 32 \]white squares.
Any domino covering two edge-adjacent squares covers exactly one black square and one white square.
Example: The Mutilated Checkerboard
Remove two opposite corner squares from an \(8\times8\) checkerboard.
Opposite corners have the same color.
Suppose two black corners are removed.
The remaining board then has
\[ 30 \]black squares and
\[ 32 \]white squares.
Every domino covers one black and one white square.
Therefore any region tiled completely by dominoes must contain equal numbers of black and white covered squares.
The mutilated board does not.
Hence,
\[ \boxed{\text{the mutilated checkerboard cannot be tiled by dominoes}.} \]What the Checkerboard Proof Is Really Tracking
One useful invariant is the difference
\[ B-W, \]where \(B\) and \(W\) are the numbers of uncovered black and white squares.
Removing one domino removes one square of each color, so
\[ (B-1)-(W-1)=B-W. \]Therefore the difference remains unchanged.
A completely tiled board would have
\[ B-W=0. \]The mutilated board begins with
\[ B-W=-2. \]So complete tiling is impossible.
Weighted Invariants
Sometimes simple counts are not preserved, but a weighted sum is.
Assign weights
\[ w_1,w_2,\ldots,w_n \]to positions or objects.
Then track
\[ I=\sum_{i=1}^{n}w_i x_i. \]If every legal move changes the individual \(x_i\) values while leaving this weighted sum unchanged, then \(I\) is an invariant.
Invariant Properties Need Not Be Numerical
An invariant can be a property rather than a number.
Examples include:
- a permutation remaining even or odd;
- a graph remaining connected;
- a configuration remaining bipartite;
- a total remaining congruent to a fixed residue class.
What matters is preservation under every allowed operation.
Reachability and Invariants
Suppose state \(T\) is reachable from state \(S\) through legal moves.
If \(I\) is an invariant, then necessarily
\[ I(T)=I(S). \]Therefore,
\[ I(T)\ne I(S) \]is enough to prove that \(T\) is unreachable.
An Invariant Gives a Necessary Condition, Not Always a Sufficient One
If two states have different invariant values, they cannot be connected by legal moves.
But if they have the same invariant value, reachability does not automatically follow.
Other obstructions may still exist.
Thus an invariant often gives a necessary condition for reachability, not a complete classification.
Example: Same Parity Does Not Guarantee Reachability
Suppose a process permits only the move
\[ n\longrightarrow n+4. \]Starting at \(1\), every reachable integer is odd.
But not every odd integer is reachable.
For example,
\[ 3 \]has the same parity as \(1\), but cannot be reached using repeated additions of \(4\).
A stronger invariant is
\[ n\pmod4. \]Finding the Right Invariant
A useful invariant is often discovered by inspecting how one legal move changes simple quantities.
Ask:
- Does the total sum change?
- Does parity change?
- Does a remainder modulo \(m\) change?
- Does a difference between two counts change?
- Does a coloring pattern stay balanced?
- Does a weighted sum remain fixed?
Test the Move, Not Just the Examples
To prove that a quantity is invariant, analyze an arbitrary legal move.
It is not enough to inspect several sample moves.
The proof must establish
\[ I(S')=I(S) \]for every allowed transition
\[ S\longrightarrow S'. \]Monovariants and Progress
A monovariant helps when a process is expected to move toward an endpoint.
Suppose
\[ M(S_{j+1})Then the process can never return to an earlier state with the same monovariant value.
This prevents cycles whenever the monovariant is determined by the state.
Strict versus Non-Strict Monovariants
A strict monovariant satisfies
\[ M(S')A non-strict monovariant may satisfy
\[ M(S')\le M(S). \]Strict change is especially useful for termination because every move makes measurable progress.
Termination from a Decreasing Integer Monovariant
Suppose \(M\) is a nonnegative integer and every legal move satisfies
\[ M(S')Why?
There is no infinite strictly decreasing sequence of nonnegative integers:
\[ M_0>M_1>M_2>\cdots\ge0. \]Eventually the process must stop.
Example: Removing Tokens
Begin with \(N\) tokens.
Each legal move removes at least one token.
Let
\[ M=\text{number of tokens remaining}. \]Every move satisfies
\[ M'\le M-1. \]Since \(M\) is a nonnegative integer, the process must terminate.
Example: Euclidean Algorithm
The Euclidean algorithm repeatedly replaces a pair
\[ (a,b) \]with a smaller remainder pair.
If
\[ a=qb+r \]with
\[ 0\le rThe second positive entry strictly decreases:
\[ b>r\ge0. \]Therefore the process cannot continue forever.
The decreasing remainder is a monovariant.
Monovariants Can Be Bounded Above Instead
A monovariant need not decrease.
It may increase strictly while remaining bounded above.
For example, if \(M\) is an integer satisfying
\[ M(S')>M(S) \]on every move and
\[ M(S)\le B \]for all states, then only finitely many moves are possible.
Monovariants Rule Out Cycles
Suppose a process returned to an earlier state:
\[ S_i=S_j \]
with \(i
If \(M\) strictly decreases on every move, then
But \(S_i=S_j\) would imply
This is impossible.
Therefore a strict monovariant forbids cycles.
Example: A Simple Sorting Monovariant
Consider a list of distinct numbers.
An inversion is a pair of positions \(i
A sorted increasing list has zero inversions.
If an algorithm repeatedly swaps adjacent out-of-order pairs, each such swap
decreases the inversion count by exactly \(1\).
Therefore inversion count is a nonnegative integer monovariant.
This proves that the swapping process must terminate.
Why the Inversion Count Works
Suppose adjacent entries
\[ x>y \]are swapped from
\[ \cdots,x,y,\cdots \]to
\[ \cdots,y,x,\cdots. \]The inversion between \(x\) and \(y\) disappears.
Their order relative to all other entries does not change in a way that alters the total inversion count beyond that one pair.
Thus the count drops by exactly \(1\).
Invariant and Monovariant Can Work Together
Some problems use both ideas.
An invariant may restrict which states are reachable, while a monovariant proves that movement cannot continue indefinitely.
Together they can classify possible terminal states or prove that a process must stop within a restricted class of configurations.
Example Pattern: Preserve Parity, Decrease Size
Suppose every move preserves
\[ n\pmod2 \]while strictly decreasing a nonnegative integer size measure \(M\).
The invariant tells us which terminal states are even possible.
The monovariant tells us that some terminal state must eventually be reached.
State Space View
A discrete process can be viewed as a directed graph.
Each state is a vertex, and each legal move is a directed edge.
An invariant partitions the graph into regions that legal moves cannot cross.
A strict monovariant assigns values that always move upward or downward along directed edges.
This viewpoint connects proof methods to graphs, algorithms, and dynamical systems.
Invariants Partition Reachability Classes
If an invariant takes values in a set \(V\), then states with different invariant values cannot be connected by legal moves.
Thus the state space may split into classes such as
\[ I(S)=0, \] \[ I(S)=1, \]and so on.
Every trajectory remains inside its initial invariant class.
Monovariants Orient the State Space
If \(M\) strictly decreases along every legal move, then every directed edge points from a larger \(M\)-value to a smaller one.
Therefore no directed cycle can exist.
In graph language, a strict monovariant provides an ordering compatible with the direction of movement.
Potential Functions
In algorithms and optimization, a monovariant is often called a potential function.
The potential assigns a numerical measure to each state.
If every operation reduces the potential, the process is making measurable progress.
This language is especially common in algorithm analysis.
Choosing a Good Monovariant
Useful candidates include:
- number of unresolved objects;
- number of inversions;
- distance from a target;
- sum of selected weights;
- maximum or minimum value;
- number of connected components;
- remaining work in an algorithm.
The best choice is one whose change can be proved for every legal move.
Common Error: A Candidate Changes in Some Moves
A quantity is not an invariant if even one legal move changes it.
Checking several convenient moves is insufficient.
Every allowed move must satisfy
\[ I(S')=I(S). \]Common Error: Confusing Constant Parity with Constant Value
If a number changes from
\[ 5 \]to
\[ 9, \]the numerical value is not invariant.
But parity is invariant because both values are odd.
Always state exactly what feature is being preserved.
Common Error: Same Invariant Value Means Reachable
If two states have the same invariant value, we cannot conclude that one is reachable from the other.
The invariant only removes impossible transitions between different classes.
Additional arguments may be required to prove reachability.
Common Error: A Monovariant Is Not Strict Enough
Suppose
\[ M(S')\le M(S) \]but equality can occur indefinitely.
Then \(M\) alone may not prove termination.
A process could keep moving forever while \(M\) remains constant.
For a direct termination proof, strict progress is usually preferable.
Common Error: No Bound on the Monovariant
A strictly decreasing real-valued quantity does not automatically prove termination.
For example,
\[ 1,\frac12,\frac14,\frac18,\ldots \]is an infinite strictly decreasing sequence bounded below by \(0\).
Termination arguments need a well-founded setting, such as a nonnegative integer that decreases strictly.
Common Error: The Target Comparison Is Missing
Finding an invariant is only part of an impossibility proof.
We must compare:
\[ I(\text{initial state}) \]with
\[ I(\text{target state}). \]The contradiction comes from showing that the target requires a different invariant value.
Common Error: The Move Rule Is Misread
Invariant proofs are highly sensitive to the exact legal operation.
If the move can occur in several forms, each form must be checked.
A quantity preserved by one version of a move may fail under another.
Common Error: Proving a Pattern from Simulation
A computer simulation may suggest that a quantity never changes.
That evidence can help discover an invariant.
But the proof still requires a general argument showing that every legal move preserves the quantity.
A Reliable Procedure for Invariant Proofs
- Write the state and legal move precisely.
- List simple quantities affected by the move.
- Test parity, modular residues, counts, differences, and weighted sums.
- Select a candidate invariant.
- Prove preservation under an arbitrary legal move.
- Compute the invariant in the initial state.
- Compute or infer it in the target state.
- If the values disagree, conclude the target is unreachable.
A Reliable Procedure for Monovariant Proofs
- Define a numerical measure \(M\) on states.
- Prove that every legal move changes \(M\) in one direction.
- Prefer strict change when proving termination.
- Identify a well-founded range such as the nonnegative integers.
- Conclude that infinite descent, infinite ascent, or cycling is impossible.
- Use terminal-state information to finish the problem when needed.
Example: Full Invariant Workflow
Start at \(11\). At every move, add or subtract \(4\). Can the process reach \(26\)?
Step 1: Identify the move.
\[ n\longrightarrow n\pm4. \]Step 2: Choose an invariant.
Since every change is a multiple of \(4\),
\[ n\pmod4 \]is invariant.
Step 3: Evaluate the initial state.
\[ 11\equiv3\pmod4. \]Step 4: Evaluate the target.
\[ 26\equiv2\pmod4. \]Step 5: Conclude.
The residues differ, so no sequence of legal moves can connect the two states.
\[ \boxed{26\text{ is unreachable}.} \]Example: Full Monovariant Workflow
Suppose a process begins with a finite list and repeatedly swaps an adjacent out-of-order pair.
Step 1: Define the measure.
Let \(M\) be the number of inversions.
Step 2: Show progress.
Each legal swap reduces \(M\) by exactly \(1\).
Thus
\[ M'\;=\;M-1. \]Step 3: Use a lower bound.
Since
\[ M\ge0 \]and \(M\) is an integer, it cannot decrease forever.
Step 4: Conclude.
The process terminates after finitely many swaps.
Practice 1: Parity Invariant
Start at \(9\). Each move adds or subtracts \(6\).
Can the process reach \(20\)? Prove your answer using an invariant.
Practice 2: Modulo \(5\)
Start at \(2\). Every move adds or subtracts \(5\).
Which residue class modulo \(5\) contains every reachable integer?
Practice 3: Checkerboard
Explain why every domino placed on an ordinarily colored checkerboard covers one black square and one white square.
What quantity does this suggest tracking in a tiling problem?
Practice 4: Necessary versus Sufficient
A move preserves parity.
If two states have the same parity, does that prove one is reachable from the other? Explain.
Practice 5: Token Removal
A game begins with \(100\) tokens. Every move removes either \(1\), \(2\), or \(3\) tokens.
Give a monovariant that proves the game must terminate.
Practice 6: Strictness
Suppose \(M\) never increases, but some legal moves leave \(M\) unchanged.
Why might \(M\) fail to prove termination?
Practice 7: Inversion Count
What is the inversion count of
\[ (3,1,2)? \]Identify the inversions.
Practice 8: Unreachable State
Start at \(4\). Each move changes the number by a multiple of \(3\).
Can the process reach \(8\)?
Practice 9: Well-Founded Descent
Why does a strictly decreasing sequence of nonnegative integers have to terminate, while a strictly decreasing sequence of positive real numbers need not?
Practice 10: Identify the Error
A student observes that a quantity stayed constant in the first twenty simulated moves and declares it an invariant.
Explain what remains to be proved.
Practice Answers
Practice 1
Every move changes the number by a multiple of \(6\), so the residue modulo \(6\) is invariant.
\[ 9\equiv3\pmod6, \]while
\[ 20\equiv2\pmod6. \]Therefore \(20\) is unreachable.
Practice 2
Every reachable integer satisfies
\[ \boxed{n\equiv2\pmod5}. \]Practice 3
Edge-adjacent checkerboard squares have opposite colors, and a domino covers two edge-adjacent squares.
Therefore every domino covers one black and one white square.
A useful quantity is the difference
\[ \boxed{B-W}. \]Practice 4
No.
Having the same invariant value is only a necessary condition for reachability. Other restrictions may still prevent one state from reaching the other.
Practice 5
Let
\[ M=\text{number of tokens remaining}. \]Each move decreases \(M\) by at least \(1\), and \(M\) is a nonnegative integer. Therefore the game must terminate.
Practice 6
The process could continue forever using moves that leave \(M\) unchanged.
Non-increase alone does not guarantee progress.
Practice 7
The inversions are
\[ (3,1) \]and
\[ (3,2). \]Therefore the inversion count is
\[ \boxed{2}. \]Practice 8
Every move preserves the residue modulo \(3\).
\[ 4\equiv1\pmod3, \]while
\[ 8\equiv2\pmod3. \]Therefore \(8\) is unreachable.
Practice 9
The nonnegative integers are discrete and well ordered. A strictly decreasing sequence cannot pass below \(0\), and each step must move to a smaller integer.
Positive real numbers can decrease forever, for example
\[ 1,\frac12,\frac14,\frac18,\ldots. \]Practice 10
The student must prove that the quantity is preserved by every legal move, not merely by the moves observed in a finite simulation.
What to Remember
An invariant remains unchanged:
\[ \boxed{I(S')=I(S).} \]A strict monovariant always moves in one direction:
\[ \boxed{M(S')- invariants are powerful for proving that target states are unreachable;
- parity, modular residues, color counts, and weighted sums are common invariants;
- same invariant value does not automatically imply reachability;
- monovariants measure progress through a process;
- strict integer-valued monovariants with appropriate bounds can prove termination;
- strict monovariants also rule out cycles;
- every legal move must be checked, not merely sampled;
- invariants and monovariants can be used together.
The central strategic question is: What simple feature of the system survives every move, or moves predictably in only one direction?
Where We Go Next
Invariants extract information that survives a sequence of moves. Another powerful discrete principle extracts certainty from limited capacity: when more objects are distributed than the available categories can keep separate, some category must repeat.
The next lesson, Pigeonhole Reasoning, develops that counting principle and its applications to repetition, collisions, divisibility, and existence arguments.