Invariants and Monovariants in Dynamical Systems

Invariants (Part 1)

Invariant is something that doesn't change after some operation. This is a very useful technique in maths, and we'll see a few applications of invariants.

Examples of invariant

For example, if we let $s(n)$ denote the sum of digits of $n$, then it is well-known that $s(n) \equiv n \pmod{9}$. So, we can say that the remainder upon division by $9$ of $n - s(n)$ is invariant.

Consider this problem :

At first, a room is empty. Each minute, either one person enters or two people leaves. After exactly $3^{1999}$ minutes, could the room contain exactly $3^{1000} + 2$ people?

The crucial fact is :

At any fixed time $t$, all the possible values of population of the room differ from one another by multiples of 3.

Indeed, if there are $n$ people in the room, then after one minute, there could be $n + 1$ or $n - 2$ people. The difference between these two possible outcomes is $3$. In $3^{1999}$ minutes, one possible population is clearly $3^{1999}$, a multiple of $3$, thus all possible populations must be a multiple of $3$, so the answer is no.

A seemingly hard problem is solved instantly with invariants. This shows the power of invariance.

Invariants (Part 2)

Parity

This is a nice problem that demonstrate the power of parity.

Let $a_1, a_2, ..., a_n$ represent an arbitary permutation of the numbers $1, 2, ..., n$. Prove that if $n$ is odd, then $(a_1 - 1)(a_2 - 2)...(a_n - n)$ is even.

This is not a hard problem. Consider the sum of the terms. Clearly, it is equal to $0$, so the sum of the numbers is invariant. However, there are odd number of $a_i - i$s, and thus one of them must be even. (or else $0$ is odd, a contradiction.). Thus, the product is even.

Invariants (Part 3)

Monovariants

Monovariants are values that is either nondecreasing all the time or nonincreasing all the time. A simple example of a monovariant is this :

Great job if you chose $n - 1$. Why is it $n - 1$? This is because the number of players in the tournament always decrease by $1$ after each game, so there must be $n - 1$ games to determine the winner.

Check out this problem here for it's problem statement and solution. This is a very clever monovariant problem by Conway. This problem is very famous. Try to solve it before looking at the solution.

That's all for this series!

Invariants are, typically, things that stay invariant (don't change) during a process. Here's an example.

Here's another example, where there's not really a process, but we can use a similar kind of reasoning (simple properties of ropes that don't depend on the specific rope) to extract the most important information (number of ropes) in an otherwise complicated scenario.

Both of the previous examples could also be thought of as part of a different (but related) strategy: https://www.expii.com/t/grouping-partitions-and-coloring-9784

But there are many other kinds of invariants too! For example, try out the problems on this topic page.