Monovariants for Proving Termination

What is a Monovariant?

A monovariant is a quantity associated with the state of a system that strictly increases or strictly decreases with each operation. The core argument is as follows:

• If a quantity always decreases with every step, and it is bounded from below (for example, it must be a non-negative integer, so it can't go below 0), then the process cannot continue indefinitely. It must stop.
• Similarly, if a quantity always increases and is bounded from above, the process must also stop.

Let's formalize this idea.

The Parliament Problem: An Algorithmic Approach

Many Olympiad problems ask you to prove that a certain arrangement is possible. A powerful strategy is to start with any random arrangement and then define an "improvement" algorithm. A monovariant can then be used to prove that this improvement process must eventually stop, leaving you with the desired arrangement.

Consider this classic problem:

In a parliament, each member has at most three enemies. Prove that the members can be separated into two houses so that each member has at most one enemy in their own house.

At first glance, it's not obvious how to construct such an arrangement. So, let's not try. Instead, let's start with a random arrangement and see if we can fix it. The resources below walk through this exact line of reasoning.

Let's break down the elegant structure of this proof, as it's a template you can use for many similar problems:

1. Define the Algorithm: Start with any random partition of members into two houses. If there is a member with two or more enemies in their own house, move them to the other house. Repeat.
2. Define the Monovariant: Let M be the total number of enemy pairs who are in the same house. This is a non-negative integer.
3. Prove it's Monotonic and Bounded: When we move a member P who has k ≥ 2 enemies in their current house (House A), the value of M decreases by k. Since P has at most 3 enemies in total, they have at most 3 - k enemies in the other house (House B). Since k ≥ 2, 3 - k can be at most 1. When P moves to House B, M increases by at most 1. The net change in M is (at most +1) + (-k). Since k ≥ 2, the change is ≤ 1 - 2 = -1. So, M strictly decreases with every move.
4. Conclude Termination: M is an integer that is strictly decreasing and is bounded below by 0. Such a process must terminate. When it terminates, it means there are no more members with 2 or more enemies in their own house. This is exactly the condition we wanted to prove is possible.

Geometric Monovariants: The Uncrossing Argument

Your interest in combinatorial geometry makes this next example particularly relevant. It's a classic problem that demonstrates how a geometric property can serve as a monovariant.

Given n red points and n blue points in the plane, with no three points collinear, show that we can draw n non-intersecting line segments, each connecting a red point to a blue point.

Again, trying to construct this matching directly is difficult. The monovariant approach is to start with any matching and improve it.

First, just connect each red point to a blue point, forming n segments. If there are no intersections, we are done. If there are intersections, like segments AD and BC below, we can perform an "uncrossing" operation.

But how do we know this process of uncrossing will ever end? We could be creating new intersections elsewhere! We need to prove this process terminates. We need a monovariant.

The proof demonstrates that for any four points forming a convex quadrilateral (like A, C, B, D in the diagram), the sum of the diagonals is always greater than the sum of two opposite sides. In our case: length(AD) + length(BC) > length(AC) + length(BD).

So, our monovariant is the total length of all n segments.

• It's a positive real number, so it's bounded below by 0.
• Every "uncrossing" operation strictly decreases its value.

Therefore, the process must terminate. When it terminates, no more uncrossing operations are possible, which means no intersections are left.

Alternative Monovariant: A simpler (but also valid) monovariant is the number of intersections. Each uncrossing operation removes at least one intersection (the one between AD and BC). While it might create new intersections with other lines, if we always pick one specific intersection and uncross it, we can design an argument where the number of crossings decreases. The sum-of-lengths argument is more robust because it guarantees a decrease regardless of which crossing you choose to fix.

Monovariants for Proving Non-Return

Finally, monovariants can also be used to prove that a process, once started, can never return to its initial state. This is shown when the monovariant changes at the first step and is strictly monotonic thereafter.

In this problem, the operation is to replace two stones at position i with one stone at i-1 and one at i+1. The monovariant M is the sum of the squares of the positions of all stones.
The change in M for one operation is:

With every move, the monovariant M strictly increases by 2. If the initial state had a monovariant value of M_0, after one move it will be M_0 + 2. It can never return to M_0. Therefore, the process can never return to its original configuration.

Practice Problems

Now it's time to construct your own monovariants. Remember the key questions: What quantity changes with each step? Can I prove it always changes in the same direction? Is it bounded?

1. (Number Manipulation) The numbers 1, 2, ..., 2n are on a blackboard. An operation consists of erasing any two numbers a and b and replacing them with |a - b|. This is repeated until only one number remains. Prove that the final number must be odd. (Hint: What is the parity of the sum of all numbers on the board? How does an operation change this sum? Consider the sum modulo 2 as your quantity of interest. Is it an invariant or monovariant?)

2. (Geometric Path) A traveler starts at a city C_1. She then travels to the city C_2 that is farthest from C_1. From C_2, she travels to C_3, the city farthest from C_2, and so on. We are given that all inter-city distances are unique, and the number of cities is finite. Prove that if her path is C_1, C_2, C_3, ... and C_3 is different from C_1, then she will never return to a city she has already visited. (Hint: Consider the length of the most recent leg of the journey as your monovariant. See Problem 5 in LINK if you need a nudge).

3. (Grid Flipping) A rectangular m x n grid is filled with real numbers. An operation consists of picking a row or a column and reversing the sign of all numbers within it. Prove that it is possible to perform a series of these operations to reach a state where the sum of numbers in each row and each column is non-negative. (This was the bonus problem in LINK. Hint: What happens to the total sum of all numbers in the grid if you flip a row/column whose sum is currently negative?)

Conclusion

You have now added monovariants to your problem-solving toolkit. You've seen that they are not just a minor variation of invariants but a powerful tool in their own right. The key takeaway is the "termination argument": a strictly monotonic and bounded quantity proves that a process must end. We've seen this applied to algorithmic constructions (the parliament problem), geometric configurations (the uncrossing problem), and numerical processes (the stones problem).

This ability to prove that an "improvement" process works is a cornerstone of advanced combinatorics and even theoretical computer science. In our next lesson, we will shift back to coloring, exploring how more sophisticated coloring schemes, such as using modular arithmetic or multiple colors, can solve challenging grid-based puzzles that go beyond simple parity checks.