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

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

  2. We can come up with simpler instances of invariants, such as # of minutes passed in the hour+# of minutes left in the hour=1hour \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:

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

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

Note by Anqi Li
7 years, 6 months ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. 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"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}


Sort by:

Top Newest

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 a2+b2+c2 a^2 + b^2 + c^2 remains same and is invariant. in this case the given triplet is not possible.

Ravi Kalyanasundaram - 7 years, 6 months ago

Log in to reply

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

Anqi Li - 7 years, 6 months ago

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?

Arkan Megraoui - 7 years, 6 months ago

Log in to reply

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

Mira B - 7 years, 6 months ago

Log in to reply


Problem Loading...

Note Loading...

Set Loading...