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:

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

tagtext 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 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 tagtext

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 $V-E+F = 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?

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:

Parity
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 $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!

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1 paragraph 2	paragraph 1 paragraph 2
`[example link](https://brilliant.org)`	example link
`> This is a quote`	This is a quote
# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"	# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"

Math	Appears as
Remember to wrap math in `\(` ... `\)` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$

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

Comments