The history of mathematics has profound roots. We can seek first traces of using algebra in works of Babylonian mathematicians tracing back to almost 4000 years ago. With firm confidence, we even can say that they had enough knowledge for solving classic quadratic equations.

Since then, mathematics was growing at a decent pace, and people created many useful mathematical instruments. When mathematicians say instruments, they usually mean methods or techniques that they use for building logical statements. After, mathematicians join these statements into separate lemmas and lemmas later transform into theorems.

Probably we will not be able to enumerate all available techniques that could be used for building theorems in mathematics. However, we can remember a few popular ones: mathematical induction and proof by contradiction. Conventional education in undergraduate schools covers these two methods very well. In this article we will try to get a glimpse into other technique that is rarely mentioned formally but has enough power to solve many interesting problems.

Introducing the Invariants

Let us assume that we have a mathematical object x and the set of transforms T. We can take any element of the set T and apply it to x to change its state. In that way, we can form a chain of different states of x.

After defining changes of our object x, we are ready to introduce our main function I. This function will be summarising any state of the object x.Potentially I may have almost any output. For example, it can output the natural number or set of rational numbers. It is crucial to be able to check equality of different outputs of the function I for different states of x.

Now if we can prove that our function I does not change its value if we apply any element of the set T to any state of x, then we can use that fact to prove logical statements. We will call I as an invariant on the set of objects x produced with the set of transforms T.

Let us consider examples from below to see how can we utilise invariants for proving logical statements.

Imaginary Islands

We will start with a simple example, and then we will try to increase complexity in a slow pace.

Let us pretend that we are imaginary people who live on the set of islands. Our task will be to formally prove that we cannot reach a particular island if a series of bridges do not connect it with our starting point.

We can walk freely inside our starting island. Because bridges connect only a few of them, we cannot reach all islands from the starting point. Let us identify each island and bridge with a number.

After it, we can introduce our invariant functions I. This function will be taking our current island where we stand and giving us a set of reachable islands as the output.

Given the scheme from above, we can enumerate all possible outputs of function I.

It is quite obvious that this function does not change its values if we move by bridges around our world because we defined it to behave like this. So if someone asked us whether we can reach island number b from the island a, we could reformulate this question in term of values of function I.

We synthetically built this example to show the main idea of using invariants, let us move to more interesting problems.

Chess puzzle

Imagine that we have got a chessboard, but not the ordinary one. Someone removed two cells from corners lying on the same diagonal.

The person who gave us this board also challenged us with a problem. He promised to give us 1000$ dollars if we will be able to fill this board using only 2⨯1 dominoes pieces.

From first glance, this problem does not sound very hard. We removed even number of cells from the original board that had 64 cells, so placing dominos that take even number of the cells does not contradict anything.

After understanding it, we will probably accept a challenge without hesitation. Who does not want to have a spare 1000$?

Author of this article made a web version of such board, so we can find and present a proof that such cover exists. Please use the left button of the mouse to place a domino and the right button of the mouse to change the direction of the domino.

After trying to fill the whole board for a while, we will start to suspect something. Thought of impossibility of covering will start to rise in our heads. Let us try to use the method of the invariants to dissect this problem.

First of all, let us define invariant function I as a difference between the number of black cells and the number of white cells on the unfilled part of the table. The initial value of this function was equal to 0, but we increased it to 2 when we removed two cells of the same colour from the board.

Second of all, we can spot that one piece of domino always covers one black and one white cell, so placing any amount of dominoes never change the value of previously defined function I.

Can we see the contradiction now? The fully covered board should have the value of I equals to 0, but we just showed that this value is impossible to reach if we place any number of dominoes.

Philosopher Max Black posted this problem in his book “Critical Thinking” in 1946.

14–15 puzzle

There is another quite famous puzzle that was proposed by the end of the 19th century by Sam Loyd. He was an American chess player who challenged the world to solve his variation of 15 puzzle.

15 puzzle is a brainteaser where we should move tiles around the board to get the initial position of tiles numbered from 1 to 15. It is not hard to find an online version of this puzzle to see how it works. This puzzle was created about ten years before Sam Loyd by Noyes Palmer Chapman from Canastota, New York. However, it became viral when Sam Loyd offered 1000$ dollars to anyone who can solve his variation of the same puzzle named 14–15 puzzle.

Sam Loyd took the initial arrangements of tiles and swapped tiles with numbers 14 and 15. The goal remained the same — find a way to get the initial position of the tiles.

How can we use the power of invariants to solve this problem? Try to work on this problem before looking further.

Let us rearrange rows of the puzzle in one straight line.

That way we can index every cell by the number i from 1 to 15 to get its value v.

We can map each move of tiles in the original puzzle into rearrangement of cells in this line.

For this line, we can calculate the number of inversions. For every value v from 1to 15 we should calculate how many values are less than v starting to the right from the position i of the cell having this value v.

If we calculate the sum of all these values, it will give us the total number of inversions.

Now, we do the trick. Sum of the row index with empty cell and the total number of inversions is always even. This way we can define our invariant function I. It will output 0 if the sum is even and 1 if the sum is odd.

We can find rigorous proof that I will not change its value with every legal move in this paper. This proof uses theory of permutations to show it.

Now we can easily see the contradiction in proposed by Sam Loyd version of 14-15 puzzle. If we swap any two adjacent cells without changing initial position of empty cell, we will increase the number of inversion by 1, so I will always have an odd number as the output. This fact shows us that it is impossible to reach the original arrangement of the board using only legal moves.

Can we go further?

Usage of invariants is not limited only to solving puzzles. We can find usage of this rich method in many areas of modern mathematics: complex analysis, the theory of differential equations and many others.

Identifying the possibility of using invariants and creation of appropriate function I for real problems could be seen as an art, and probably it is why mathematicians are falling in love with this branch of science.

I hope that this story also will help someone to love mathematics a little more.