Invariants and Monovariants

Adithya Bhaskar
January 24, 2016

1 Introduction
Invariants and monovariants: these are two very important topics for the IMO.
These terms by themselves do not need much explanation: Invariants ae quan-
tities that are preserved during some process, and monovariants are quantities
that either only increase or only decrease. These are very helpful in analyz-
ing simple/complex algorithms and processes which often find their way into
various olympiads like the USAMO, USA TST, IMO, India TST and Russian
Olympiads to name a few. That seems to be enough introduction, so let’s get
on to solving problems! Recline and enjoy!

2 Invariants
As mentioned above, some things just don’t change! For warmup, we present
the following two problems. A tip: When looking for invariants, try to keep the
quantity symmetric in all the variables!

Warmup 1. The numbers 1, 2, ..., 2016 are written on a blackboard. Every

minute, two numbers a, b on the blackboard are erased and are replaced by ei-
ther their sum or their difference. After 2015 moves, a number n is left. What
is the parity of n?

Solution. It is clear that here we are looking for parity-related stuff so we try
the parity of the sum of all the numbers written : it clearly works (a+b and a−b
have the same parity). Since 1 + ... + 2016 = 1008 · 2017 is even, we conclude
that n is even.

Warmup 2. (IMOTC 2013) The numbers 1, 2, ..., 100 are written on a black-
board. A move is defined as follows: select two numbers a, b written, erase them
and instead write ab + a + b. After 99 moves, exactly one number is left. Find
all possible values of this number.

Solution. Motivation: We notice that the quantity ab+a+b is of degree 2 so we

try something like (a+x)(b+x). Take x = 1 to get ab+a+b+1 = (a+1)(b+1).

1
Yay! So all we do is take (a1 +1)(a2 +1)...(an +1) where the ai ’s are the numbers
currently on the blackboard. This is an invariant. Hence the final number can
have only one value: 2.3....101 = 101!.

Now let’s see how this can be applied to harder problems:

1. (IMO 1993) The following game is played on an infinite chessboard: Initially,

each cell of an n × n square is occupied by a chip. A move consists of a jump
of a chip over a chip in the horizontal or vertical direction onto a cell directly
behind it. The chip jumped over is removed. Find all values of n, for which the
game ends with one chip left over.

Solution. (Official) Suppose that one can play the game on a 3k × 3k square
so that at the end only one piece remains. Denote the cells by (i, j), i, j ∈
{1, ..., 3k}, and let S0 , S1 , S2 denote the numbers of pieces on those squares
(i, j) for which i + j gives remainder 0, 1, 2 respectively upon division by 3. Ini-
tially S0 = S1 = S2 = 3k 2 . After each move, two of S0 , S1 , S1 diminish and
one increases by one. Thus each move reverses the parity of the Si ’s, so that
S0 , S1 , S2 are always of the same parity. But in the final position one of the Si ’s
must be equal to 1 and the other two must be 0, which is impossible.
Here’s some (not much) motivation: we see that 3 × 3 and 6 × 6 boards don’t
suffice after some fooling about. This gives the idea of (mod 3).
There is a part of the solution left: namely, that the required is possible for
all other boards. We do not cover that in this article, but leave a hint: use
induction.

We leave a few problems for the reader to try:

1. ([1]) In the Parliment of Sikinia, each member has at most three enemies.
Prove that the house can be separated into two houses, so that each member
has at most one enemy in his own house.

2. (IMOTC 2006) There are n markers, each with one side white and the other
side black. In the beginning, these n markers are aligned in a row so that their
white sides are all up. In each step, if possible, we choose a marker whose white
side is up (but not one of the outermost markers), remove it, and reverse the
closest marker to the left of it and also reverse the closest marker to the right of
it. Prove that, by a finite sequence of such steps, one can achieve a state with
only two markers remaining if and only if n − 1 is not divisible by 3. (Beware!
You may require some knowledge of algorithms for this one!)

3. (Russia 1995) There are three boxes of stones. Sisyphus moves stones one by
one between the boxes. Whenever he moves a stone, Zeus gives him the number
of coins that is equal to the difference between the number of stones in the box
the stone was put in, and that in the box the stone was taken from (the moved
stone does not count). If this difference is negative, then Sisyphus returns the

2
corresponding amount to Zeus (if Sisyphus cannot pay, generous Zeus allows
him to make the move and pay later). After some time all the stones lie in their
initial boxes. What is the greatest possible earning of Sisyphus at that moment?

4. (India TST 2004) The game of pebbles is played as follows. Initially there
is a pebble at (0, 0). In a move one can remove a pebble from (i, j) and place
one pebble each on (i + 1, j) and (i, j + 1), provided (i, j) had a pebble to begin
with and (i + 1, j) and (i, j + 1) did not have pebbles. Prove that at any point
in the game there will be a pebble at some lattice point (a, b) with a + b ≤ 3.

3 Monovariants
Personally, I find monovariants very interesting, so probably this section will
be larger than the previous one. Before we start, a tip. Often you shall have
to quote ”This quantity keeps decreasing, but it has a lower bound so...”; and
the easiest lower bound is for squares: they are never negative. For this reason,
most (but not all) monovariants you encounter will probably be of the form of
the sum of squares or the squares of sums! Another common monovariant is the
absolute value of the sum : this is particularly helpful if we are changing just
signs of numbers! Okay, so let’s start with a relaively simple example:

1. (Russia 1961) Real numbers are written in an m × n table. It is permissible

to reverse the signs of all the numbers in any row or column. Prove that after
a number of these operations, we can make the sum of the numbers along each
line (row or column) nonnegative.

Solution. Note that after each operation, the sum of all the entries of the table
increases. But it clearly has an upper bound. RIP problem.

2. (IMO Shortlist 2007/C4) Let A0 = {a1 , a2 , ...., an } be a finite sequence of

real numbers. For each k ≥ 0 we form a sequence Ak = {x1 , x2 , ..., xn } we
construct a new sequence Ak+1 in the following way:
(i) We choose a partition {1,P I ∪ J, where I and J are two disjoint
2, ..., n} = P
sets, such that the expression | i∈I xi − j∈J xj | is minimized. (We allow I
or J to be empty). If there are several such partitions, one is chosen arbitrarily.
(ii) We set Ak+1 = {y1 , y2 , ..., yn } where yi = xi + 1 if xi ∈ I, and yi = xi − 1
if i ∈ J.
Prove that for some k, the sequence Ak contains an element x such that
|x| ≥ n2 .

Solution. We provide a slightly long but fully intution based solution: since we
are dealing with mods 0 is an important number. We first define the following:
For a sequencePAk , we denote by Ik and Jk the corresponding sets I, J.
Further let ck = ( i∈I xi − j∈J xj )2 . Assume the contrary. Then we shall
P
4
show that ck keeps increasing; since the contrary is true, ck ≤ ( ak )2 ≤ n4
P

3
will give a contradiction. Our proof is based on this lemma:

Lemma. We have ck ≤ ( n2 )2 for all k.

Proof. Assume not. Since all ai ’s have absolute valuePless thanPn2 we can move
an ai from I to J or vice versa, reducing the value of | i∈I xi − j∈J xj |, hence
it was possible to have a smaller value of ck ; contradiction.
So now on with the proof. We have a(say) = | i∈I xi − j∈J xj | ≤ n2
P P
thus for the new Ak+1 this value is at least (− n2 ) + n = n2 ≥ a, and equality
can’t hold because of our first assumption (that the statement of the problem
is false). Hence we have established our monovariant, and.... the problem has
been solved.

The following problem was considered to be the hardest one of IMO 1986, but
it’s life expectancy is simply not enough ;):

3. To each vertex of a regular pentagon an integer is assigned, so that the

sum of all five numbers is positive. If three consecutive vertices are assigned
the numbers x, y, z respectively, and y < 0, then the following operation is
allowed: x, y, z are replaced by x + y, −y, z + y respectively. Such an operation
is performed repeatedly as long as at least one of the five numbers is negative.
Determine whether this procedure necessarily comes to an end after a finite
number of steps.

Solution. Experimenting leads to concluding that the answer must be yes. We

have already emphasised that squares are important. Let us assume x3 = y < 0;
and suppose we apply the operation be applied at this vertex. Consider the
quantity
Q = (xi − xi+1 )2
P

where the subscripts are cyclic. Note that Q changes by 2sy < 0 where s is
the sum of all the written numbers (s is invariant, so s > 0!). Hence Q takes
only nonnegative integer values, and keeps decreasing. This cannot continue
indefinitely, so yes, the process must stop.

4. (Romania TST 2002) After elections, every parliament member (PM), has
his own absolute rating. When the parliament set up, he enters in a group and
gets a relative rating. The relative rating is the ratio of its own absolute rating
to the sum of all absolute ratings of the PMs in the group. A PM can move
from one group to another only if in his new group his relative rating is greater.
In a given day, only one PM can change the group. Show that only a finite
number of group moves is possible.

Solution. Squares, squares, squares! Our first try is the quantity S equal to
the sum of the squares of all the relative ratings. And it works!! We leave it to
the reader to check that this quantity always decreases...

4
Try out a few problems on your own. Beware, they are not meant to be easy!
(The last two are pretty easy, so these are ordered very loosely by difficulty)

1. (Famous, can be found in [2]) We have n(n+1)

2 stones in k piles. In each move
we take one stone from each pile and form a new pile with these stones (if a pile
has only one stone, after that stone is removed the pile vanishes). Show that
regardless of the initial configuration, we always end up with n piles, having
1, 2, . . . , n stones respectively.

2. (BAMO 2006) We have k switches arranged in a row, and each switch points
up, down, left, or right. Whenever three successive switches all point in different
directions, all three may be simultaneously turned so as to point in the fourth
direction. Prove that this operation cannot be repeated infinitely many times.

3. (Hungary 1990) You are on a pogo stick on the coordinate plane and can
jump around in the following manner: from (x, y) you can jump to one of the
points (x, y + 2x), (x, y − 2x),(x + 2y, y),(x − 2y, y) and when you leave a point
√
you cannot return to it on the next jump. Suppose that you start at (1, 2),
prove that you can never return there.

4. ([1]) In the Parliament of Sikinia, each member has at most three enemies.
Prove that the house can be separated into two houses, so that each member
has at most one enemy in his own house.

5. (IMO Shortlist 2012) Several positive integers are written in a row. Itera-
tively, Alice chooses two adjacent numbers x and y such that x > y and x is to
the left of y, and replaces the pair (x, y) by either (y + 1, x) or (x − 1, x). Prove
that she can perform only finitely many such iterations.

6. (IMO Shortlist 2014) We have 2m sheets of paper, with the number 1 written
on each of them. We perform the following operation. In every step we choose
two distinct sheets; if the numbers on the two sheets are a and b, then we erase
these numbers and write the number a + b on both (not one) sheets. Prove that
after m · 2m−1 steps, the sum of the numbers on all the sheets is at least 4m .

4 References
[1] Problem Solving Strategies, Arthur Engel

[2] Olympiad Combinatorics, Pranav A Sriram

http://www.artofproblemsolving.com/community/q1h601134p3568667

[3] Various posts at Artofproblemsolving,

http://www.artofproblemsolving.com