Invariant Principle

Generally speaking, an invariant is a quantity that remains constant during the execution of a given algorithm. In other words, none of the allowed operations changes the value of the invariant. The invariant principle is extremely useful in analyzing the end result (or possible end results) of an algorithm, because we can discard any potential result that has a different value for the invariant as impossible to reach.

Consider a set of states \(S = (s_1, s_2, \dots, s_n)\), and a set of transitions \(T \subseteq S \times S\), defined as follows: \((s_i, s_j) \in T\) if and only if we can transition from state \(s_i\) to state \(s_j\). An invariant with respect to \(T\) is a function \(f: S \rightarrow \mathbb{R}\) such that \((s_i,s_j) \in T \implies f(s_i)=f(s_j)\).

In particular, given a starting state \(s_1\) and a rule for transitions, invariants allow us to determine which states we can reach from \(s_1\).

Many problems give the starting state and the transition rule, then ask whether a certain result is achievable (or equivalently, ask which results are achievable). For example,

Alice writes the numbers 1, 2, 3, 4, 5, and 6 on a blackboard. Bob selects two of these numbers, erases both of them, and writes down their sum on the blackboard. For example, if Bob chose the numbers 3 and 4, the blackboard would contain the numbers 1, 2, 5, 6, and 7. Bob continues until there is only one number left on the board. What are the possible values of that number?

---

In this problem, the invariant is the sum of the numbers on the blackboard, \(n\). If Bob chooses to erase the numbers \(a\) and \(b\), he will write \(a+b\) on the blackboard, making the new sum \(n-a-b+(a+b)=n\), so \(n\) is indeed an invariant. This means that at any time during the process, the sum of the numbers on the blackboard will be \(n=1+2+3+4+5+6=21\), which means that the final number must be 21.

In a more formal sense, the states of this problem are possible sets of numbers on the blackboard, and the starting state is \(s_1=\{1, 2, 3, 4, 5, 6\}.\) The transition in this problem is erasing two numbers and writing their sum. The invariant function, \(f(S)\), is the sum of the numbers in \(S,\) and the invariant rule is verified as above. Therefore, since \(f(s_1)=21,\) the end state \(S_{\text{final}}\) must also satisfy \(f(S_{\text{final}})=21,\) and since \(S_{\text{final}}\) has only one number, it must be 21. \(_\square\)

Although the invariant was able to determine precisely what would happen in the previous problem, they are usually only able to determine what cannot happen. For example, if the problem was slightly changed as follows:

Alice writes the numbers 1, 2, 3, 4, 5, and 6 on a blackboard. Bob selects two of these numbers, erases both of them, and writes down their positive difference on the blackboard. For example, if Bob chose the numbers 3 and 4, the blackboard would contain the numbers 1, 1, 2, 5, and 6. Bob continues until there is only one number left on the board. What are the possible values of that number?

Then many different results are possible. However, invariants are still useful in excluding possibilities:

If Bob chooses the numbers \(a\) and \(b\), where \(a \geq b,\) the sum changes from \(n\) to \(n-a-b+(a-b)=n-2b\). Therefore, the sum always changes by an even number, meaning \(n \pmod{2}\) is an invariant. Originally, the sum of the numbers on the board is \(1+2+3+4+5+6=21\), so at any point of the process, the sum of the numbers must be odd. Therefore, the final number cannot be even. \(_\square\)

Note that the invariant says nothing about whether all odd final results are possible; it merely says that no even results are possible.

A monovariant is very similar to an invariant, but instead of remaining unchanged under transitions, monovariants either increase or decrease under transitions. They are very useful in showing algorithms terminate; for example, if a particular monovariant is a positive integer that decreases at every step of an algorithm, the algorithm must eventually terminate since decreasing integers cannot stay positive forever.

In more formal language, a monovariant with respect to \(T\) is a function \(f: S \rightarrow \mathbb{R}\) such that \((s_i,s_j) \in T \implies f(s_i)>f(s_j)\), or a function \(f: S \rightarrow \mathbb{R}\) such that \((s_i,s_j) \in T \implies f(s_i)<f(s_j)\).

Note that the definition uses \(>\) and \(<\) rather than \(\geq\) and \(\leq\). This is because if an algorithm can leave the monovariant equal to its previous value, it becomes much less useful at demonstrating the algorithm terminates. However, if it can be shown that the algorithm must change the value of the monovariant in a finite number of steps, then the non-strict inequality would be sufficient.

As a general rule, invariants are useful whenever several different actions are possible, and especially when a problem asks whether a specific result is possible. In particular, invariants are especially helpful in the analysis of combinatorial games, where the potential transitions are given by legal moves, and the result asked about is the winner of the game.

Alice and Bob have a large chocolate bar, in the shape of a \(10 \times 10\) grid. Each turn, a player may either eat an entire bar of chocolate, or break any chocolate bar into two smaller rectangular chocolate bars along a grid line. The player who moves last loses. Who wins this game? (adapted from NIMO)

---

Every turn, the number of chocolate bars either increases by one (if the player breaks a chocolate bar into two chocolate bars), or decreases by one (if the player eats a chocolate bar). Therefore, the number of chocolate bars Alice will have to choose from is invariant modulo 2. At the beginning of the game, Alice has only one chocolate bar to choose from. Since the players cannot break the chocolate bar forever (since they must break the chocolate along grid lines), eventually Alice will have to eat the final piece of chocolate, so Bob wins regardless of how the players choose to play the game. \(_\square\)

In more advanced problems, the use of invariants will not be set up in such an obvious manner. In those cases, it is usually necessary to transform the problem into a transitional one in some way. Many coloring problems fall under this category. For example, a problem asking whether is it possible to tile some shape with dominoes can be considered a transitional problem, where the starting state is the whole shape, the set of transitions is removing two adjacent squares, and the end state is an empty board.

Two opposite corners are removed from a standard chessboard. Is it possible to tile the resulting board with dominoes?

---

Suppose that the removed corners were both white squares. In every transition, we remove one white square and one black square, so \(S=(\text{black squares})-(\text{white squares})\) is invariant. Originally, there are 32 black squares and 30 white squares, so \(S=2\) at any point. The empty board has \(S=0\), so it is impossible to reach it from the original board; in other words, the board cannot be tiled by dominoes. \(_\square\)

Many problems will also use monovariants in a non-obvious way, usually by asking to prove that some arrangement is possible. These problems are often solved by beginning with a random arrangement, describing an algorithm that improves the situation at each step, and showing the algorithm terminates with the help of a monovariant.

In the parliament of Sikinia, each member has at most three enemies. Prove that the house can be separated into two houses, so that each member has at most one enemy in his own house. (Engel, Problem Solving Strategies, p.2)

---

Initially, separate the members into two houses in any manner. Let \(H\) be the total sum of all enemies each member has in his own house. Now suppose there is a person \(A\) who has at least two enemies in his own house. Then he has at most one enemy in the other house, so if \(A\) switches houses, \(H\) will decrease. Since \(H\) is necessarily a non-negative integer, it cannot decrease forever, so at some point this process ends. This means we cannot any longer find a person who has at least two enemies in their own house, which is precisely the assignment requested. \(_\square\)

Another big clue that a problem involves invariants is being asked to prove something for all possible inputs, such as points in a plane. A common strategy to try in these problems is picking a random point, and examining what changes when the point is moved around.

As the first two problems showed, the sum of all the numbers (possibly modulo some constant) is a common invariant to try. More generally, a weighted sum is often useful, such as \(a+2b+4c+8d+16e\) or \(a-b+c-d+e-f\). When dealing with transforming lists of numbers, another common invariant is the number of inversions, or pairs \((i,j)\) such that \(i<j\), but the \(i^\text{th}\) element is bigger than the \(j^\text{th}\) element. For example, the list \((5, 1, 2, 3, 4)\) has four inversions.

A common monovariant to look out for, when dealing with tuples of numbers, is distance from the origin. In many cases, the set of transitions will either cause the distance from the origin to always decrease, often demonstrating that the end result must be \((0,0,\dots, 0)\); in some cases, this is even an invariant.