This will be quite a long introduction, so please bear with me.
Note: I assume the reader has familiarised himself with Introduction to Invariance Principle
Invariants are particularly useful in analysis of games, transformations and questions of the like. Basically, the main motivation behind applying the invariance principle is to find something that does not change, when something is repeated, whence the important usage of this in algorithms. Quoting Problem-Solving Strategies, here is a non-exhausted list to keep in mind when applying invariance.
Can a given state be reached?
Find all reachable end states.
Is there convergence to an end state?
Find all periods, if possible.
To kick off the discussion, let us start with some real life examples of invariants:
How do we know whether we can untie this knot without cutting any of the strings? Untying here means turning a knot into the unknot. Even better, how do we know that the following Ochiai knot is actually the unknot?
This is one of the long-standing problems that involves the concept of invariance. Here, we associate each knot with a polynomial.The Alexander–Conway polynomial is actually defined in terms of links, which consist of one or more knots entangled with each other. This is motivated from the Reidemeister Move. It requires defining the following:
You can read more about how the conway polynomial is defined recursively here.
Euler's Famous Formula regarding the correlation between edges, faces and vertices. The concept of an invariant is something that holds under all circumstances, and Euler's famous theorem can be proven to hold for ALL polyhedra. So it actually provides an invariance for some intriguing problems in olympiads. By the way, Euler's formula states that .
We can come up with simpler instances of invariants, such as . Can you come up with similar such invariants?
Moving on... Let us go back to talking about olympiads.
Also, if you are ambitious and want to use this in olympiad combinatorics problems, here's a few common invariants that we will encounter along the way:
Colouring (as in the more commonly known checkerboard colouring and others)
Sum of squares/products or things of the like
For starters, here's a simple invariance problem:
An ordered triple of numbers is given. It is permitted to perform the following operation on the triple: to change two of them, say or , to and . Is it possible to obtain the triple from the triple using this operation?
Look forward to the next post in days time to learn more about invariants!