Invariants and monovariants

This chapter introduces the powerful concepts of invariants and monovariants, essential tools for analyzing discrete processes and move-based games. Mastery of these techniques is crucial for solving a significant class of problems in combinatorics, frequently appearing in competitive examinations to determine game outcomes or process termination.

---

Chapter Contents

|

| Topic |

|---|-------| | 1 | Move-based games | | 2 | Invariant idea | | 3 | Monovariant idea | | 4 | Process termination questions |

---

We begin with Move-based games.

Part 1: Move-based games

Move-based Games

Overview

Move-based games and state-evolution problems are central in combinatorics. A position changes by legal moves, and the real question is usually not “what happens next?” but “what can never change?”, “what must keep changing?”, or “what structure is forced by a greedy rule?”. In CMI-style questions, this topic often mixes invariants, monovariants, parity, extremal arguments, and optimality proofs. The 2025 PYQ around card stacks is a perfect example: a legal move rule creates a structured process, and the proof requires showing that some order is preserved, some quantity grows in a controlled way, and the final greedy outcome is optimal. ---

Learning Objectives

---

Core Idea

---

The Three Main Tools

---

Parity and Reachability

---

Order-Based Processes

This is exactly what happens in the stack-building PYQ: although cards arrive in arbitrary order, the top cards of the stacks become ordered under the greedy rule. ---

Greedy Stack Process

Why this matters: If top cards increase left to right, then a new card is placed at the earliest possible valid position, and the stack system stores a lot of hidden information about subsequences. ---

Longest Increasing Subsequence Connection

This is a deep and beautiful fact:

• the stacks encode a lower bound on possible increasing subsequences,

• and increasing subsequences force at least that many stacks in any legal decomposition.

So greedy is not just valid; it is optimal. ---

Why Greedy Optimality Usually Needs Two Proofs

For the stack PYQ:

• greedy creates exactly $k$ stacks,

• every increasing subsequence of length $k$ forces at least $k$ stacks,

• hence no strategy can do better.

---

Minimal Worked Example

Example Process the sequence $\qquad 3,\ 7,\ 2,\ 5,\ 6,\ 4,\ 9,\ 8$ using the greedy stacking rule.

• $3$: start stack 1

• $7$: cannot go on $3$, so start stack 2

• $2$: place on stack 1

• $5$: place on stack 2

• $6$: start stack 3

• $4$: place on stack 2

• $9$: start stack 4

• $8$: place on stack 4

Final stack tops are $\qquad 2,\ 4,\ 6,\ 8$ which increase left to right. Also, the sequence has an increasing subsequence of length $4$, for example $\qquad 3,\ 5,\ 6,\ 8$ so the final number of stacks is $4$. ---

Typical Proof Structures

---

Winning Strategies in Move-Based Games

Even when a problem is not explicitly about two-player winning strategy, this way of thinking helps in analyzing legal moves and forced structure. ---

Common Techniques for This Topic

---

Common Mistakes

---

CMI Strategy

---

Practice Questions

:::question type="MCQ" question="In a move-based process, a quantity that never changes after any legal move is called" options=["a monovariant","an invariant","a subsequence","a greedy bound"] answer="B" hint="Focus on the word 'never changes'." solution="A quantity that remains unchanged after every legal move is called an invariant. Therefore the correct option is $\boxed{B}$." ::: :::question type="NAT" question="A process starts with the number $10$. Each legal move subtracts $2$. After exactly $4$ legal moves, what number is obtained?" answer="2" hint="This is a direct state update." solution="Each move subtracts $2$. So after $4$ moves, the total decrease is $\qquad 4\cdot 2 = 8$ Hence the new value is $\qquad 10-8=2$ So the answer is $\boxed{2}$." ::: :::question type="MSQ" question="Which of the following are standard useful tools in move-based games?" options=["Invariants","Monovariants","Parity arguments","Ignoring the legality of moves"] answer="A,B,C" hint="Think of standard proof techniques." solution="Invariants, monovariants, and parity are standard tools. Ignoring legal move conditions is never valid. Hence the correct answer is $\boxed{A,B,C}$." ::: :::question type="SUB" question="Explain why a monovariant can be used to prove that a process must terminate." answer="Because it moves only in one direction and cannot do so indefinitely if bounded." hint="Think about a quantity that always decreases or always increases." solution="Suppose a quantity $M$ is associated to every state, and every legal move makes $M$ strictly decrease. If $M$ is bounded below, then the process cannot continue forever, because an infinite strictly decreasing sequence of integers cannot exist. Similarly, if $M$ strictly increases but is bounded above, the process must terminate. Hence a bounded monovariant proves termination." ::: ---

Summary

---

---

Part 2: Invariant idea

Invariant Idea

Overview

An invariant is a quantity or property that remains unchanged throughout an allowed process. In combinatorics and discrete mathematics, invariants are one of the strongest tools for proving that something is impossible, or that the system can only end in certain types of states. In CMI-style problems, the real challenge is usually not computation, but finding the right quantity that stays fixed. ---

Learning Objectives

---

Core Idea

---

The Basic Strategy

---

Most Common Types of Invariants

---

Example Patterns

Pattern 1: Parity invariant If every move changes the number of heads by $-2$, $0$, or $+2$, then the parity of the number of heads never changes. So starting from an even number of heads, you can never reach an odd number of heads. --- Pattern 2: Coloring invariant If each move always covers one black and one white square on a checkerboard, then the difference $\qquad \text{(number of uncovered black squares)} - \text{(number of uncovered white squares)}$ behaves predictably and can reveal impossibility. This is the core idea behind many tiling problems. --- Pattern 3: Sum modulo $m$ If every move changes the total by a multiple of $3$, then the total modulo $3$ is invariant. This is stronger than just checking the ordinary sum. ---

Minimal Worked Examples

Example 1 A pile contains an even number of stones. In one move, you may add $2$ stones or remove $4$ stones. Can the pile ever contain an odd number of stones? Each move changes the number of stones by an even number, so parity is invariant. Since the initial number is even, it always remains even. So an odd number of stones is impossible. --- Example 2 A board is colored in black and white like a chessboard. Suppose every move removes two adjacent squares. Why might coloring help? Any adjacent pair contains one black and one white square. So every move removes one black and one white square. Hence the difference between the number of black and white squares removed stays balanced, and this can prove certain tilings impossible. ---

Standard High-Value Invariants

---

What an Invariant Can Prove

---

Common Mistakes

---

CMI Strategy

---

Practice Questions

:::question type="MCQ" question="Eight coins lie on a table, all showing tails. In one move, exactly two coins are flipped. Which of the following numbers of heads is impossible to obtain?" options=["$2$","$4$","$6$","$7$"] answer="D" hint="Track the parity of the number of heads." solution="Initially the number of heads is $0$, which is even. Flipping exactly two coins changes the number of heads by $-2$, $0$, or $+2$, so the parity of the number of heads remains even. Therefore an odd number of heads is impossible. Among the options, only $7$ is odd. Hence the correct option is $\boxed{D}$." ::: :::question type="NAT" question="Eight coins lie on a table, all showing tails. In one move, exactly two coins are flipped. How many different values can the number of heads take?" answer="5" hint="Use parity, then check attainability." solution="The parity of the number of heads is invariant, so only even values are possible. Starting from $0$ heads, the possible values are $\qquad 0,2,4,6,8$. All of these are achievable by choosing suitable pairs to flip. Hence the number of different possible values is $\boxed{5}$." ::: :::question type="MSQ" question="Which of the following are useful invariant ideas in discrete problems?" options=["Parity of a quantity","Residue modulo $m$","A board coloring pattern","A quantity that strictly decreases after every move"] answer="A,B,C" hint="An invariant stays unchanged; a strictly decreasing quantity is a different idea." solution="Parity, residue classes, and coloring arguments are all standard examples of invariants. A quantity that strictly decreases is not an invariant; it is a monovariant. Therefore the correct answer is $\boxed{A,B,C}$." ::: :::question type="SUB" question="A standard chessboard has two opposite corner squares removed. Explain why the remaining board cannot be tiled by dominoes, where each domino covers exactly two adjacent squares." answer="Impossible by coloring invariant" hint="Color the board black and white." solution="Color the board in the usual black-white checkerboard pattern. Every domino placed on the board covers exactly one black square and one white square, because adjacent squares have opposite colors. Now remove two opposite corners. Opposite corners of a chessboard have the same color. So removing them removes two squares of the same color. The remaining board therefore has unequal numbers of black and white squares. Since each domino covers one black and one white square, any domino tiling would cover equal numbers of black and white squares. That is impossible here. Therefore the board cannot be tiled by dominoes. Hence the answer is $\boxed{\text{Impossible by coloring invariant}}$." ::: ---

Summary

---

---

Part 3: Monovariant idea

Monovariant Idea

Overview

A monovariant is a quantity that always moves in one direction during a process: it always increases or always decreases. Unlike an invariant, it does not stay fixed. In CMI-style problems, monovariants are used to prove that a process must stop, that cycles are impossible, or that certain states cannot repeat. ---

Learning Objectives

---

Core Idea

---

Why Monovariants Matter

---

The Basic Strategy

---

Common Monovariants

---

Strict vs Non-Strict

---

Standard Example: Inversions

---

Minimal Worked Examples

Example 1 Suppose you repeatedly swap adjacent out-of-order entries in a list until the list is sorted. The inversion count decreases by $1$ at each such swap, and it can never become negative. Therefore the process must terminate. --- Example 2 Start with two unequal positive integers $(a,b)$. Replace the larger one by the difference of the two numbers. Then quantities like $\qquad a+b$ and $\qquad \max(a,b)$ strictly decrease while remaining nonnegative. So the process cannot continue forever without eventually reaching equality or zero structure, depending on the exact rule. ---

Monovariant Versus Invariant

---

Boundedness Principle

This is one of the most useful proof templates in discrete mathematics. ---

Common Mistakes

---

CMI Strategy

---

Practice Questions

:::question type="MCQ" question="In a sorting process, one repeatedly swaps adjacent inverted pairs. Which quantity is a natural monovariant?" options=["Sum of all entries","Product of all entries","Number of inversions","Set of values appearing"] answer="C" hint="Think of a measure of disorder." solution="Swapping an adjacent inverted pair reduces the disorder of the arrangement. The standard quantity that tracks this disorder is the inversion count, and it decreases by exactly $1$ at each such swap. Therefore the correct option is $\boxed{C}$." ::: :::question type="NAT" question="How many inversions are there in the sequence $(4,1,3,2)$?" answer="4" hint="Count pairs $(i,j)$ with $i<j$ and $a_i>a_j$." solution="The inversions are: $(4,1)$, $(4,3)$, $(4,2)$, and $(3,2)$. So the total number of inversions is $\boxed{4}$." ::: :::question type="MSQ" question="Which of the following can serve as monovariants in suitable discrete processes?" options=["A quantity that strictly decreases each move","Number of inversions in adjacent-swap sorting","Maximum value in a process where the larger number is replaced by a smaller one","A quantity that is preserved exactly at every move"] answer="A,B,C" hint="A monovariant moves in one direction." solution="A monovariant changes in one direction. A strictly decreasing quantity is a monovariant, inversion count is a classic monovariant in sorting, and the maximum value can be a monovariant in certain number processes. A quantity preserved exactly is an invariant, not a monovariant. Hence the correct answer is $\boxed{A,B,C}$." ::: :::question type="SUB" question="Explain why a process cannot continue forever if there is a nonnegative integer-valued quantity that strictly decreases after every move." answer="Strictly decreasing nonnegative integer monovariant implies termination" hint="Use the fact that nonnegative integers cannot decrease indefinitely." solution="Let the quantity be $M$. By assumption, $M$ is always a nonnegative integer, and after every move its value strictly decreases. So if the process continued forever, we would get an infinite strictly decreasing sequence of nonnegative integers: $\qquad M_0 > M_1 > M_2 > \cdots$ But such a sequence cannot exist, because nonnegative integers cannot decrease indefinitely. Therefore the process must stop after finitely many moves. Hence the answer is $\boxed{\text{Strictly decreasing nonnegative integer monovariant implies termination}}$." ::: ---

Summary

---

---

Part 4: Process termination questions

Process Termination Questions

Overview

Process termination questions ask whether a repeated operation must eventually stop. In discrete mathematics, the standard tools are invariants, monovariants, and the well-ordering principle. In CMI-style problems, the real challenge is to find a quantity that cannot keep changing forever. ---

Learning Objectives

---

Core Idea

Termination is usually proved by finding a monovariant that cannot continue changing forever. ---

Most Important Principle

---

Other Useful Termination Frameworks

---

How to Find a Good Monovariant

The best monovariant is usually:

• easy to compute,

• integer-valued,

• forced to move in one direction.

::: ---

Minimal Worked Examples

Example 1 A positive integer $n$ is repeatedly replaced by $\lfloor n/2\rfloor$. Show that the process terminates. At each step, the value of $n$ remains a non-negative integer and strictly decreases whenever $n>0$. So $n$ is a decreasing non-negative integer monovariant. Hence the process must terminate. --- Example 2 Given two positive integers $(a,b)$ with $a\ge b$, replace $(a,b)$ by $(a-b,b)$ whenever $a>b$. Show that the process terminates. Consider the sum $\qquad S=a+b$ After one move, $\qquad S'=(a-b)+b=a<S$ So the sum strictly decreases and stays a non-negative integer. Hence the process terminates. ---

Termination Versus Final Outcome

---

When Invariants Help but Are Not Enough

---

Common Patterns

---

Common Mistakes

---

CMI Strategy

---

Practice Questions

:::question type="MCQ" question="Which of the following is sufficient to prove that a process terminates?" options=["A quantity remains constant throughout the process","A non-negative integer quantity strictly decreases at every step","A quantity is sometimes smaller than before","The process has a legal move at every stage"] answer="B" hint="Think about infinite descent." solution="A process must terminate if there is a non-negative integer quantity that strictly decreases after every move, because such a quantity cannot decrease indefinitely. Hence the correct option is $\boxed{B}$." ::: :::question type="NAT" question="A positive integer $n$ is repeatedly replaced by $\lfloor n/2\rfloor$. Starting from $n=20$, after how many steps does the process first reach $0$?" answer="5" hint="Write the successive values." solution="The successive values are $\qquad 20\to 10\to 5\to 2\to 1\to 0$ So the process reaches $0$ after $\boxed{5}$ steps." ::: :::question type="MSQ" question="Which of the following statements are true?" options=["A strictly decreasing sequence of non-negative integers must terminate","An invariant alone is always enough to prove termination","A bounded increasing sequence of integers must eventually stop increasing","If a process has finitely many states and no state repeats, it must terminate"] answer="A,C,D" hint="Think about well-ordering and finite state spaces." solution="1. True. Infinite descent in non-negative integers is impossible.

False. Invariants do not usually prove termination by themselves.

True. An increasing integer sequence that is bounded above can only increase finitely many times.

True. In a finite state space, an infinite non-repeating process is impossible.

Hence the correct answer is $\boxed{A,C,D}$." ::: :::question type="SUB" question="Show that the process on positive integers defined by $n\mapsto n-1$ for $n>0$ must terminate." answer="The process terminates because $n$ is a non-negative integer monovariant that strictly decreases at each step" hint="Use $n$ itself as the measure." solution="Consider the quantity $M=n$. At each step, when $n>0$, the rule replaces $n$ by $n-1$. Therefore $M$ strictly decreases by $1$. Also, $M$ is always a non-negative integer. Since there cannot be an infinite strictly decreasing sequence of non-negative integers, the process must terminate. Thus the process terminates." ::: ---

Summary

---

Chapter Summary

---

Chapter Review Questions

:::question type="MCQ" question="A standard $8 \times 8$ chessboard has all squares initially white. A move consists of choosing any $2 \times 2$ square and flipping the colors of all four squares within it (white becomes black, black becomes white). Can you reach a state where exactly one square is black?" options=["Yes, by carefully chosen moves.","No, because the parity of the total number of black squares is an invariant.","Yes, if the board size was $2^n \times 2^n$.","No, because the sum of row parities is invariant."] answer="No, because the parity of the total number of black squares is an invariant." hint="Consider the total number of black squares. How does its parity change with each move?" solution="Let $B$ be the total number of black squares. Initially, $B=0$. When a $2 \times 2$ square is chosen, its four squares' colors are flipped. Each square changes from white to black (+1 to $B$) or black to white (-1 to $B$). Thus, the number of black squares in the chosen $2 \times 2$ block changes by $k_1 \cdot 1 + k_2 \cdot (-1)$, where $k_1$ is the number of white squares that become black, and $k_2$ is the number of black squares that become white, with $k_1+k_2=4$. The net change in $B$ is $(k_1 - k_2)$. Since $k_1+k_2=4$, we have $k_1-k_2 = k_1 - (4-k_1) = 2k_1-4$, which is always an even number. Therefore, the parity of the total number of black squares, $B \pmod 2$, is an invariant. Since $B$ starts at 0 (even), it must always remain even. Reaching a state with exactly one black square ($B=1$, odd) is impossible."
:::

:::question type="NAT" question="You have a list of numbers $(a_1, a_2, \dots, a_n)$. In one step, you choose any two numbers $a_i$ and $a_j$ (where $i \neq j$) and replace both with $\min(a_i, a_j)$. This process continues until all numbers are equal. If you start with $(5, 2, 8, 2)$, what is the final common value of all numbers?" answer="2" hint="Consider the minimum value among the numbers. What can be said about it throughout the process?" solution="Let $S$ be the set of numbers. In each step, we choose $a_i, a_j \in S$ and replace them with $\min(a_i, a_j)$. Notice that any number in the set can only decrease or stay the same, as it is replaced by a value less than or equal to itself. Specifically, the minimum value in the set, $\min(S)$, is a non-decreasing monovariant (it can only stay the same or increase if a smaller number is replaced by a larger one, but that's not the case here, as we replace both with the minimum).
Let's trace the example:
Start: $(5, 2, 8, 2)$

Choose $a_1=5, a_3=8$. Replace both with $\min(5,8)=5$. The list becomes $(5, 2, 5, 2)$.

Choose $a_1=5, a_2=2$. Replace both with $\min(5,2)=2$. The list becomes $(2, 2, 5, 2)$.

Choose $a_3=5, a_4=2$. Replace both with $\min(5,2)=2$. The list becomes $(2, 2, 2, 2)$.

All numbers are now equal. The process terminates. The final common value is 2.
More generally, the process must terminate because the sum of the numbers is a non-increasing integer-valued monovariant, bounded below by $n \times \min(\text{initial numbers})$. The final common value must be the minimum of the initial set of numbers. This is because no number can ever become smaller than the initial minimum, and any number larger than the initial minimum will eventually be replaced by the minimum when paired with it. The initial minimum is 2."
:::

:::question type="MCQ" question="On a circular track, there are 2023 lamps. Initially, exactly one lamp is on, and the rest are off. A move consists of choosing any two adjacent lamps and flipping their states (on to off, off to on). Can you reach a state where all lamps are off?" options=["Yes, by carefully selecting adjacent lamps.","No, because the number of 'on' lamps is a monovariant that always decreases.","No, because the parity of the number of 'on' lamps is an invariant.","Yes, if the number of lamps was even."] answer="No, because the parity of the number of 'on' lamps is an invariant." hint="How does flipping two adjacent lamps affect the total count of 'on' lamps?" solution="Let $k$ be the number of 'on' lamps. When two adjacent lamps are chosen and their states are flipped, there are three possibilities for how $k$ changes:

Both lamps are off: Both become on. $k \to k+2$.

Both lamps are on: Both become off. $k \to k-2$.

One lamp is on, one is off: The 'on' lamp becomes off, the 'off' lamp becomes on. $k \to k$.

In all cases, the change in $k$ is an even number ($+2$, $-2$, or $0$). This means the parity of the number of 'on' lamps, $k \pmod 2$, is an invariant.
Initially, exactly one lamp is on, so $k=1$, which is an odd number.
The target state is all lamps off, so $k=0$, which is an even number.
Since the parity of $k$ must remain odd, it is impossible to reach a state where $k=0$. Therefore, the process cannot reach a state where all lamps are off."
:::

---

What's Next?