Invariants and monovariants
By Ryan Ng
An invariant is a quantity/object that does not change during a process or action. A monovariant is a quantity/object that changes monotonically—either always increases, or always decreases. This is a difficult concept to understand theoretically—you’ll have a better time understanding with the below examples. The right invariant or monovariant can simplify difficult questions significantly.
Example 1: There are 10 red, 11 blue, and 12 green chameleons. Sometimes, two chameleons meet. If they are the same colour, nothing happens. If they are different colours, they will both change to the third colour. Can all chameleons ever be the same colour?
We will take all three quantities modulo 3—in other words, we will take the remainder when the red, blue and green chameleon counts are divided by 3. So we have the remainders:
Red: 1 (mod 3)
Blue: 2 (mod 3)
Green: 0 (mod 3)
Nothing happens in the first action, where two same-colour chameleons meet, so we can ignore it. In the second action, we decrease two of of the quantities by 1 and increase the other by 2.
Now, notice that 2 (mod 3) ≡ -1 (mod 3) — the remainders of 2 and -1 when divided by 3 are the same. Let’s see what happens when we subtract our three numbers by 1. Then we’d get:
Red: 0 (mod 3)
Blue: 1 (mod 3)
Green: -1 (mod 3) ≡ 2 (mod 3)
It turns out that when two chameleons transform, the remainders are still (0, 1, 2), just in different order. This is our invariant: the combination of remainders (0, 1, 2) stays constant. Now, for all chameleons to be the same colour, two of the chameleon counts must be 0 (and 0 divided by 3 has remainder 0). The combination (0, 1, 2) only has one 0. Therefore, all chameleons can never be the same color.
Example 2: Athan goes to the casino to play the following game: At the start of every round, he bets $1. If he wins, he wins $2 and if he loses, he gets nothing. He starts with $5 and stops when he runs out of money. Prove that Athan can’t stop after an even number of rounds.
Each round, Athan either wins $1 or loses $1. Because -1 ≡ 1 (mod 2), we can just add $1 to his balance mod 2 after each round, similar to the previous question.
Take Athan’s balance modulo 2, to get 5 ≡ 1 (mod 2). Since we add 1 after each round, to simulate an even number of rounds, suppose 2k rounds have passed where k is an integer. Then his balance would be 1 + 2k (mod 2). Since 2k is even, the remainder is just 1; in other words 1 + 2k ≡ 1 (mod 2). This means so his balance cannot be zero. The invariant chosen here is Athan’s balance modulo 2.
Example 3: 2000 people are distributed among the rooms of a 115-room mansion. Each minute, as long as not all the people are in the same room, somebody walks from one room into a different room with at least as many people. Prove that eventually all the people will be gathered in one room.
This is solved using an increasing monovariant. We have a situation here where a quantity (people) is getting concentrated into a smaller and smaller number of rooms. Whenever we have something related to concentration, we can use squares, because squaring numbers magnifies them significantly—so concentrating values into one square, rather than spreading them out, will magnify the quantity more. For example, n2 + k2 < (n + k)2 = n2 + k2 + 2nk.
We can use a sum of squares as the monovariant. Suppose xm represents the number of people in the mth room. Let’s write our monovariant quantity as the following.
A = x12 + x22 + x32 + x42 + …… + x1152
Now, the more concentrated people are into a smaller number of rooms, the bigger the total should be. Let’s suppose two rooms, x3 and x4, undergo our process—where someone walks from one room to another that has at least as many people. Let’s say someone from Room 3 walks into Room 4, and it’s required that x4 ≥ x3. We can look at only the x32 + x42 terms for now because the rest doesn’t change. Then this will change into:
(x3 - 1)2 + (x4 + 1)2 = x32 - 2x3 + 1 + x42 + 2x4 + 1 = x32 + x42 + 2(x4 - x3) + 2
Since x4 ≥ x3, our quantity has increased by a positive value equal to 2(x4 - x3) + 2. This means the concentration of people into fewer rooms is increasing, each time someone moves. Even when x4 = x3, the sum of squares still increases by 2 at minimum. This means any movement will always increase concentration, and this must occur until we hit our concentration limit, which is where everyone is in the same room.
Example 4: In the sequence 1, 0, 1, 0, 1, 0, 3, 5, … each term starting with the seventh is equal to the last digit of the sum of the preceding six terms. Prove that this sequence does not contain six consecutive terms equal to 0, 1, 0, 1, 0, 1, respectively.
If you would like a challenge, feel free to try this. The solution may make you think, how did anyone think of that? If you would like a hint or solution, read as much of the following as you’d like. I won’t be as pedantic here as the previous examples because this is a little more advanced.
Suppose xn is the nth term of the sequence. Let’s define a function:
f(x1, x2, x3, x4, x5, x6) = 1x1 + 2x2 + 3x3 + 4x4 + 5x5 + 6x6.
If we had a sequence of numbers 0, 1, 0, 1, 0, 1, then for some values in the sequence
xn … xn+5,
f(xn … xn+5) = 12 ≡ 2 (mod 5).
Let’s look at the second subsequence, from x2 … x7. Then we have
f(x2 … x7) = x2 + 2x3 + 3x4 + 4x5 + 5x6 + 6x7
And because x7 is the last digit of the preceding 6 numbers added, we can add them together and take the remainder when divided by 10, to represent x7:
f(x2 … x7) = x2 + 2x3 + 3x4 + 4x5 + 5x6 + (6(x1 + x2 + x3 + x4 + x5 + x6) mod 10)
Taking mod 5 on this expression, we have the following.
= x1 + 2x2 + 3x3 + 4x4 + 5x5 + 6x6 + (5(x1 + x2 + x3 + x4 + x5 + x6) mod 10) (mod 5)
Since the last term is a multiple of 5, it is 0 mod 5. So this simplifies to
= x1 + 2x2 + 3x3 + 4x4 + 5x5 + 6x6 (mod 5)
So the function mod 5 of the second subsequence, is the same as the first subsequence with x1 … x6. This is general: each subsequence plugged into this function is the same as the previous subsequence, when taking the remainder when divided by 5. The first six terms are 1, 0, 1, 0, 1, 0, which makes f(x1 … x6) = 9 ≡ 4 mod 5. So every subsequence will be 4 mod 5 when plugged into the function. Because the sequence 0, 1, 0, 1, 0, 1 would be 2 mod 5, it is never possible.
The invariant here is this weighted sum mod 5. Though the function’s form seems out of the blue, the motivation was to create a weighted sum that differentiates between 0, 1, 0, 1, 0, 1 and 1, 0, 1, 0, 1, 0. It’s likely that a different choice of coefficients could work.