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:

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

No vote yet

1 vote

×

Problem Loading...

Note Loading...

Set Loading...

$</code> ... <code>$</code>...<code>."> Easy Math Editor

`*italics*`

or`_italics_`

italics`**bold**`

or`__bold__`

boldNote: you must add a full line of space before and after lists for them to show up correctlyparagraph 1

paragraph 2

`[example link](https://brilliant.org)`

`> This is a quote`

Remember to wrap math in $</span> ... <span>$ or $</span> ... <span>$ to ensure proper formatting.`2 \times 3`

`2^{34}`

`a_{i-1}`

`\frac{2}{3}`

`\sqrt{2}`

`\sum_{i=1}^3`

`\sin \theta`

`\boxed{123}`

## Comments

Sort by:

TopNewestVery 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.

Log in to reply

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.

Log in to reply

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?

Log in to reply

Thanks so much for posting this. These are great examples and I look forward to reading your other notes!

Log in to reply