Invariance and Monovariance Principle

Consider the following question: Ahmed has a bunch of $50 and $20 bills. Is it possible for him to have exact change to purchase a new iPhone for $567? We observe that the bills all end with a 0 (are multiples of 10), and hence, we know that no matter what combination of bills he uses, he would be unable to get a dollar amount that doesn't end with a 0.

In the above example, we use the fact that all bills are multiples of 10, to help us classify certain dollar values which cannot be attained. While this method does not give all dollar values which Ahmed does not attain (for example, he can't attain $30), the method is sufficient to conclude that he cannot attain $567.

When solving problems involving sequences, recursions, or iterative processes, in which we want to determine if a certain state can be achieved, there are two related tools that can help us. An invariant is a property whose value stays constant when transformations are applied to the object of interest. If the desired result has a different value for that property, then we can never arrive at that result. A monovariant is a property whose value only changes in one direction. It will either always increase or always decrease. In the above example, we could say that "The invariant property is that the last digit is always 0, hence it can never be 7!"

Determining an invariant or a monovariant is sometimes obvious from the given conditions, and sometimes much more difficult because no clear quantity can be easily determined. After we have shown that the quantity is an invariant or monovariant, we then need to demonstrate why it is sufficient to help us reach our conclusion.

When we have an invariant, we can easily show that a final state cannot be achieved if the value of the property differs from the initial state. However, it doesn’t tell us that every state which has the same property value can be achieved. Instead, we will need to construct a series of transformations which explicitly show why those states can be reached.

When we have a decreasing (resp. increasing) monovariant, we can easily show that a final state cannot be achieved if the value of the property is higher (resp. lower) than that in the initial state. Once again, it doesn’t necessarily tell us which states can be achieved and we will still need an explicit construction.

Worked Examples

1. Grayson writes the numbers 1 to 1000 on a blackboard. He then randomly chooses two numbers $a$ and $b$ from the list to erase, and replaces them with the number $a-b$. If he continues this process until he is left with a single number on the board, is it possible for him to be left with the single number 657?

Solution: There are a lot of numbers on the board to start, so we can’t realistically try a sequence of operations to see what number we end up with. Since we're replacing $a$ and $b$ with $a-b$, it is clear that the sum of the numbers will always decrease. However, while this is a valid monovariant, it is not sufficient for us to conclude that we can't reach 657, nor does it explain how we can reach 657.

However, this can motivate us to look at the sum of the numbers that are on the board. At the start, this sum is $\sum_{i=1}^{1000} i = \frac{1000*1001}{2} = 500500$. When Grayson chooses two numbers $a$ and $b$ to erase, and adds $a - b$ to the list, the new total will be $500500 - a - b + (a-b) = 500500 - 2b$.

This suggests that we should look at the sum of the numbers on the board modulo 2. The sum starts out as $0 \pmod{2}$ and always remains $0 \pmod{2}$ when we perform an operation. Hence, this quantity is an invariant! Since the sum of the numbers on the board will always be even, we cannot get to a position where there is a single odd number written on the board.

2. $n$ red points and $n$ blue points are drawn in the plane with no 3 points collinear. Show that we can find a set of $n$ segments joining the blue points to the red points so that no pair of segments crosses.

Solution: One way we could approach this problem is to randomly join the points together by segments and then try to uncross any pairs of crossing segments. This would turn the question into an iterative question, as we are performing an operation repeatedly, so it is a good place to look for an invariant or monovariant. Our main concern here is that the process may never stop, so we want to look for a monovariant, something that either always increases or always decreases.

Let $S$ be the sum of the lengths of the segments we have drawn between the points. If we have a pair of crossing segments, then the 4 endpoints form the vertices of a quadrilateral, and the segments form the diagonals. If we uncross this pair of segments, the new segments will be two opposite sides of the quadrilaterals (which pair will depend on the colouring of the vertices, but it does not matter to us). The triangle inequality tells us that the sum of the lengths of these two segments is less than the sum of the lengths of the starting segments.

So we have our monovariant. Each time we perform one of these swaps, the sum of the lengths of the segments decreases. This means that we will never arrive back at the same set of lines we had. There are $n!$ different ways we could have drawn the segments to join the points together, so we will eventually not be able to perform any more swaps, and will be left at a configuration with no crossings.

Note: We turned the problem into an iterative problem in order to have something that was changing so that we could get a monovariant.

3. Starting with the points $(-5,10),(8,7),(-3,4),(6,5),(9,4)$ in the Cartesian plane, we allow the following two operations: either choose a point and move it one unit up, then choose a second point and move it one unit to the right, or choose a point and move it one unit down, then choose a second point and move it one unit to the left. Determine all points $(x,y)$ such that after a finite sequence of operations, all 5 points can end up on the point $(x,y).$

Solution: In this question, we have to determine all possible end states, which makes the problem harder than the previous problems. If we have an end state where all the 5 points are on $(x,y)$, then we can clearly move each of them in succession, till they are on $(x+1, y+1 )$. Similarly, we could also move them till they are all on $(x-1, y-1)$. This tells us that the answer will look like a set of lines (or possibly no lines at all). It further strongly suggests that $x - y$ will be a constant!

Let's define $X$ to be the sum of the 5 x-coordinates, and $Y$ to be the sum of the 5 y-coordinates. Then, $X$ and $Y$ either both increase by 1, or both decrease by 1, hence $X-Y$ is an invariant. It is easy to calculate that the starting value of $X-Y$ is $-15$. Hence, if all the 5 points are on $(x,y)$, we must have $5x - 5y = -15$, or that $y = x + 3$.

This immediately tells us that the set of possible end states must lie within the line $y = x + 3$. It remains to show that this can be achieved. The easiest way to do so, is to adjust each point till they reach $(0,3)$, and then use the first paragraph to show that all integer points on the lie $y = x + 3$ can be reached.