×

# Elementary Techniques used in the IMO (International Mathematical Olympiad) - Invariants

This will be quite a long introduction, so please bear with me.

Invariants Part $$1$$

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:

1. Consider the following knot, more commonly known as the trefoil knot:

tagtext

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?

tagtext

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:

tagtext

You can read more about how the conway polynomial is defined recursively here.

1. 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 $$V-E+F = 2$$.

2. We can come up with simpler instances of invariants, such as $$\text{# of minutes passed in the hour} + \text{# of minutes left in the hour} = 1 \text{hour}$$. Can you come up with similar such invariants?

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:

1. Parity

2. Colouring (as in the more commonly known checkerboard colouring and others)

3. 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 $$a$$ or $$b$$, to $$\frac{a+b}{\sqrt{2}}$$ and $$\frac{a-b}{\sqrt{2}}$$. Is it possible to obtain the triple $$(1,\sqrt{2},1+\sqrt{2})$$ from the triple $$(2, \sqrt{2}, \frac{1}{\sqrt{2}})$$ using this operation?

Look forward to the next post in $$2$$ days time to learn more about invariants!

Note by Anqi Li
3 years, 7 months ago

Sort by:

Very interesting. This is the first time I am reading about invariant. I think I found the solution for the simple invariant problem you posed (not simple for me). sum of the squares of individual terms of the triplet is invariant. For he triplet a,b,c $$a^2 + b^2 + c^2$$ remains same and is invariant. in this case the given triplet is not possible. · 3 years, 7 months ago

Nice. Refer to my post: Part 2 of Invariance for the solution and more. In fact, Part $$3$$ has already been posted with more examples. · 3 years, 7 months ago

Nice invariance problem:

Given any arrangement of white and black tokens along the circumference of a circle, we're allowed the following operations- take out a white token and change the colour of both its neighbours, or put in a white token and change the colour of both its neighbours. Is it possible to go from a configuration with just two tokens, both white, to a configuration with two tokens, both black? · 3 years, 7 months ago