Maths

Download as pdf or txt
Download as pdf or txt
You are on page 1of 15

Semi-invariants IMOTC 2013 Simple semi-invariants

These are some notes (written by Tejaswi Navilarekallu) used at the International Mathematical
Olympiad Training Camp (IMOTC) 2013 held in Mumbai during April-May, 2013.
1 Introduction
It is quite often that we see problems in Olympaids which involve making moves to change a given
conguration. A typical problem would have a given initial conguration, rules that every move
should follow, and a nal desired conguration. The moves can be completely deterministic, or can
depend on certain choices (like in games). The task might be, for example, to show that a nal
conguration cannot be achieved, or to count the number of moves required to get to a certain
conguration.
In this note, we shall explore a plethora of such problems and discuss a particular technique of
associating (semi-)invariant quantities to the congurations.
2 Simple semi-invariants
As we shall see below, a key concept in problems with moves is to associate a quantity, an invariant
or a semi-invariant, to each possible conguration such that it changes uniformly with every move
(or remains unchanged for that matter). Typical uniformity we will see is the (strict) monotonicity.
If, for example, the semi-invariant is a positive integer that strictly decreases with every move, then
by induction on this semi-invariant it follows that we can make only nitely many moves. This is
a standard way to attack many problems and we shall see this being used repeatedly below. We
shall sometime hide the semi-invariant and only consider the induction, but the ideas behind each
of them will be similar.
Let us start with the following (very) simple example.
Example 2.1. Let n be a positive integer. Written on a board are n natural numbers x
1
, x
2
, . . . , x
n
.
A move consists of replacing two numbers on the board by their sum (until there is only one number
on the board). Then the number on the board at the end is independent of the choices of moves.
It is clear from the description of a move that the number of integers on the board reduces
with every move. This is our rst example of a semi-invariant! For a conguration C of a bunch
of numbers on the board, we dene I(C) to be the number of integers in this conguration. If a
move takes C to C

then I(C

) = I(C) 1 < I(C). Therefore we will end up with one number


after exactly n1 moves. This sounds like a complicated way of making a simple observation, but
we shall consider less trivial semi-invariants soon.
Consider a move that replaces two numbers x and y on the board by x+y. As mentioned above,
we want to associate each conguration with a quantity that changes uniformly. Given that we are
replacing the numbers by their sums, it is natural that the sum of the numbers on the board
changes uniformly. In fact, the sum does not change at all. More precisely, for any conguration
C, let J(C) denote the sum of all the numbers on the board in that conguration. If a move takes
C to C

then we have J(C) = J(C

). Therefore J is an invariant. Hence it follows that the number


on the board at the end is J(C
0
) = x
1
+ x
2
+ + x
n
(with C
0
the initial conguration), which is
independent of the choices of moves.
That was a lengthy explanation for a very simple example. Let us make it a bit more interesting
by changing the example slightly.
1
Semi-invariants IMOTC 2013 Simple semi-invariants
Example 2.2. Written on a board are the numbers 1, 2, 3, . . . , 2013. In a move, Alice can choose
two numbers x and y on the board and replace them with x y. Can Alice make 2012 moves in
such a way that the nal number on the board is 1000?
This example diers from the previous one only by a sign, i.e., we have x y instead of x + y
as part of the rule. Since we already know some nice invariant for the previous example, let us
instead look for the similarity between the two. As a more general observation, the (only) similarity
between xy and x+y is their parity. That is, either both of them are odd, or both are even. This
hints that if we consider the same quantity J(C) as in the previous example, then even though
it may not remain invariant under a move, its parity will. To be precise, for a conguration C
of numbers on the board, let J(C) denote the sum of all those numbers. Then J(C) (mod 2) is
invariant under a move. Since the sum of all the numbers on the board initially is odd and 1000 is
even, it follows that the desired nal conguration cannot be achieved.
Problem 2.3. Written on a blackboard are n nonnegative integers whose greatest common divisor
is 1. A move consists of erasing two numbers x and y, where x y, on the blackboard and replacing
them with the numbers x y and 2y. Determine for which original n-tuples of numbers on the
blackboard is it possible to reach a point, after some number of moves, where n1 of the numbers
on the blackboard are zeros.
Discussion. Let us start examining the semi-invariants. A move replaces two numbers x and y
with x y and 2y. What is evident at rst sight is that the sum of the numbers remains the same
after any move. There is another simple observation we can make. Note that we eventually want
many zeros on the board. A move that erases two numbers x and y, with y = 0, will replace those
numbers back, and hence it has no eect. Therefore any zero that appears on the board will remain
forever. Thus the number of zeros on the board can never decrease, so the number of zeros on the
board is a semi-invariant. This semi-invariant is a non-negative integer, increases monotonically
with every move and is bounded above by n. Unfortunately, it is not a strictly increasing function,
so we need something else.
Working out examples is in our opinion one of the best ways to get an insight. This is one of
the few aspects that we shall repeat every now and then! When working out examples, it is most
often the best to start with the simplest possible ones. In this problem, we can start with n = 2
and with numbers 1, a on the board. As we proceed with the rst few values of a we can guess
that the desired end point is reached if and only if a = 2
k
1 for some k 0. We can try to work
out some more examples with a, b > 1 on the board to start with and we see in all the cases that
a + b is a power of two. If we now have more than two numbers on the board in the beginning,
then to get to the desired end conguration we have to pass a stage in which there are exactly two
non-zero numbers on the board. From what we have guessed so far, the sum of these two numbers
should be a power of two. Since the sum of all the numbers on the board is an invariant our guess
should be that a
1
+a
2
+ +a
n
= 2
k
for some k 0, where a
1
, a
2
, . . . , a
n
are the numbers on the
board.
Let us go back to the case n = 2. If a and b are the numbers on the board in the beginning,
then for their sum to be a positive power of 2 we need both of them to be of the same parity. They
cannot both be even since they should be coprime to each other (by the given condition of the
problem), and hence they are both odd. After the rst move, we are left with two even numbers. It
is evident that henceforth all the numbers that appear on the board will be even. We can therefore
remove a factor of 2, or rather a factor of a power of 2, and reduce the case back to odd numbers.
2
Semi-invariants IMOTC 2013 Simple semi-invariants
Thus the power of two dividing the gcd of the two numbers increases (strictly) at every stage. This
is an excellent semi-invariant! In fact, the same semi-invariant works in the general case. As we
have observed that the gcd is what we need to consider, we note that either (x y, 2y) = (x, y) or
(x y, 2y) = 2(x, y). This will be the key in the solution below. In the solution below, we shall
not explicitly consider the semi-invariant, but it is there in a hidden form.
Solution. We shall show that we can reach the desired conguration if and only if the sum of all
the numbers on the board is a power of two.
We make two observations. Firstly, the sum of all the numbers on the board is invariant under
a move and secondly, (x y, 2y) = (x, y) or (x y, 2y) = 2(x, y). Since the gcd of the numbers to
start with is 1 it follows that the gcd of the numbers on the board is a power of 2 after any number
of moves. If we can reach a point where n 1 of the numbers are zero, then the non-zero number
at this stage is a power of two. But, by the rst observation, this is the sum of all the numbers at
the beginining. This proves the only if implication.
Our third observation is that if we have the numbers a
1
, a
2
, . . . , a
n
on the board, then we can
reach the desired conguration by making moves if and only if we can do the same with the numbers
a
1
/d, a
2
/d, . . . , a
n
/d on the board, where d = (a
1
, a
2
, . . . , a
n
).
Now suppose that a
1
a
2
. . . a
n
are n non-negative integers on the board such that
a
1
+ a
2
+ + a
n
= 2
k
, with k 0. We shall show by induction on k that we can reach the
desired conguration. The statement is obvious if k = 0. Suppose that k > 0. Then the number of
odd numbers among a
1
, a
2
, . . . , a
n
is even. Pair them up in any order and for each pair (x, y) with
x y, replace them with x y and 2y (i.e., make a move with these numbers). Note that both
x y and 2y are even, and therefore we will end up with all even numbers, say b
1
, b
2
, . . . , b
n
. Since
b
1
/2+b
2
/2+ +b
n
/2 = 2
k1
it follows by the induction hypothesis that we can reach the desired
conguration starting with the numbers b
1
/2, b
2
/2, . . . , b
n
/2. By the third observation, we can
therefore reach the desired conguration starting with the numbers b
1
, b
2
, . . . , b
n
. This completes
the induction step and concludes the solution.
Problem 2.4. Let M be a set of six distinct positive integers whose sum is 60. These numbers are
written on the faces of a cube, one number to each face. A move consists of choosing three faces
of the cube that share a common vertex and adding 1 to the numbers on those faces. Determine
the number of sets for which it is possible, after a nite number of moves, to produce a cube all of
whose sides have the same number.
Discussion. Note that the desired conguration in this problem is not an end conguration since
we can get dierent congurations if we make more moves thereafter. So we are not really interested
in a semi-invariant, but rather we are looking for some invariant. Let us make the notation a bit
more precise, and we shall see immediately what we need to look for.
We let i, j = 1, 2, 3 in this entire paragraph. Let A
i
and B
i
denote the opposite faces of the cube
and let a
i
and b
i
denote the numbers on them respectively. Then a move consists of choosing one
face from each of {A
i
, B
i
} and increasing the number on it by 1. So for any i, the sum a
i
+ b
i
will
increase by 1. Therefore the dierence of two such sums is an invariant. Thus to get the desired
conguration it is necessary to have these sums equal.
For the converse, we have to make the right choices of the moves to make all the numbers equal.
This is not very dicult we can make the numbers on each of the opposite sides equal.
3
Semi-invariants IMOTC 2013 Simple semi-invariants
Solution. For i = 1, 2, 3, let A
i
and B
i
denote the opposite faces of the cube and let a
i
and b
i
denote the numbers on them respectively. Then for any 1 i, j 3, the quantity a
i
+ b
i
a
j
b
j
is invariant under a move. Therefore, if after nite number of moves, all the sides have the same
number then a
i
+ b
i
= 20 for all i = 1, 2, 3. Thus M = {x, y, z, 20 x, 20 y, 20 z} where x, y, z
are integers with 1 x < y < z 9, and there are
_
9
3
_
= 84 such possible sets.
Conversely, suppose that M is one of these 84 sets. We may assume that a
i
b
i
for i = 1, 2, 3
and that b
1
a
1
b
2
a
2
b
3
a
3
. We add (b
1
a
1
)/2+(b
3
a
3
)/2 to the faces containing a
1
, a
2
and a
3
, (b
2
a
2
)/2 (b
1
a
1
)/2 to the faces containing b
1
, a
2
and a
3
, and (b
3
a
3
)/2 (b
2
a
2
)/2
to the faces containing b
1
, b
2
and a
1
. It is easy to see that all the numbers added are integers. With
these moves we will have all the numbers equal to b
3
.
Problem 2.5 (USAMO 2003, Problem 6). At the vertices of a regular hexagon are written six
nonnegative integers whose sum is n. One is allowed to make moves of the following form: (s)he
may pick a vertex and replace the number written there by the absolute value of the dierence
between the numbers written at the two neighbouring vertices. Prove that if n is odd then one can
make a sequence of moves, after which the number 0 appears at all six vertices.
Discussion. There are two semi-invariants that we can think of at rst sight: the number of zeros
and the maximum of the six numbers. The former is monotonic only if we choose our moves carefully
(otherwise this number could both increase and decrease). The latter however is a monotonically
decreasing quantity. The only instance in which this latter quantity cannot be reduced further is
when we have the numbers a, a, 0, a, a, 0 at the vertices (in that order), a deadlock situation. So if
we somehow make sure that this conguration is never reached then we can get to all zeros. We
cannot blindly keep reducing one of the largest numbers, because the conguration a+1, a, 0, a, a, 0
will then result in a deadlock. So we have to be bit more careful.
The given condition that n is odd is quite crucial (note that the deadlock situation has the sum
even). One can therefore try to keep the sum of all numbers odd (unless all the numbers become
zero). This may not be possible after every move, but we can group the moves together such that
this is the case. Such grouping was also part of the solution to Problem 2.3, albeit in a hidden way.
To say a little bit more about such groupings, note that we have either one, three or ve odd
numbers to start with. It is a common idea to reduce many such possibilities to one which is
most suited to the situation. In this case, there is no such conguration that is most suited. Some
congurations might be more intuitive to one and some to the others. Here we give one reason
why the solution below is chosen among many possible ones. Remember that we want to reduce
the maximum value. If this maximum value is even and is adjacent to vertices with odd numbers,
then we can reduce the value without changing the conguration type. For this purpose, it is good
to have even and odd numbers at every alternate vertices. We therefore consider this as a special
conguration and try to reduce every other conguration to this.
Solution. By an odd conguration C we mean six non-negative numbers C = (a
1
, a
2
, . . . , a
6
) such
that

6
i=1
a
i
is odd. Let t
k
denote the operation at vertex k, i.e., replacing a
k
with |a
k1
a
k+1
|,
with k written modulo 6. If M(C) denotes the maximum of the six numbers, then note that
application of t
k
will not increase the value of M. We call an odd conguration C very odd if the
six numbers are alternatively odd and even. The following two-step algorithm terminates since after
every application of Step 2 to a conguration C we get a conguration C

with M(C

) < M(C) or
C

= (0, 0, 0, 0, 0, 0).
4
Semi-invariants IMOTC 2013 Moving on with moves
Step A. Suppose that C is odd but not very odd. Suppose rst that we have ve odd
numbers. Then we may assume that C (1, 1, 1, 1, 1, 0) (mod 2). Then apply t
2
and t
4
to
get a very odd conguration.
Suppose that we have three odd numbers, but they are not on the alternative vertices. Then
there are two possibilities (after symmetry): C (1, 1, 1, 0, 0, 0) or C (1, 1, 0, 1, 0, 0) modulo
2. In the former case apply t
4
and t
6
to reduce to the case of ve odd numbers, and in the
latter case apply t
6
followed by t
1
to get a very odd conguration.
Finally suppose that we have one odd number. Then we may assume that C (1, 0, 0, 0, 0, 0)
(mod 2). Then apply t
2
and t
6
to reduce to the previous case.
Step B. Suppose that C is very odd, so C (1, 0, 1, 0, 1, 0) (mod 2). Applying t
2
, t
4
and t
6
if necessary, we may assume that M(C) is odd. If M(C) = a
1
then apply t
3
and t
5
to get an
odd conguration C

with M(C

) < M(C), and then go to Step A. We take similar actions if


M(C) = a
3
or M(C) = a
5
. If M(C) = a
1
= a
3
= a
5
, the apply t
2
, t
4
, t
6
followed by t
1
, t
3
, t
5
to get (0, 0, 0, 0, 0, 0) and terminate the algorithm.
3 Moving on with moves
We have seen a few problems with simple semi-invariants. We now move on to slightly more involved
quantities. Some of these are not very easy to nd, but we shall give some intuitive arguments
towards obtaining them.
Problem 3.1 (IMO 1986, Problem 3). To each vertex of a regular pentagon an integer is assigned
so that the sum of all ve 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 ve numbers is negative. Determine whether this procedure necessarily comes to an end after
a nite number of steps.
Discussion. Considering a few examples with small numbers, one should quickly guess that the
procedure necessarily comes to an end after a nite number of steps. It is then a question of assigning
a semi-invariant that changes monotonically with every operation. There are many possible choices
for this. First let us look at some quantities that fail to serve the purpose. Before anything else,
note that the sum of all the numbers is an invariant. A natural quantity to look at in such cases
is the sum of all the squares. A simple calculation then tells us that this is not monotonic with
respect to the operations.
The next (wrong) guess could be the minimum of the ve numbers. If x, y, z are all negative,
then we have bigger negative numbers than before. This leads to the intuition that if a negative
number is next to a positive number then the value of the semi-invariant should be better. In
other words, the quantity should take into account the neighbours of every vertex. We can therefore
consider

|a
i
+a
i+1
| or

(a
i
+a
i+1
)
2
where a
i
s are the numbers at the vertices and the index i is
taken modulo 5. After an operation, these quantities will have terms of the form |a
i
| (or a
2
i
), and of
the form |a
i
+a
i+1
+a
i+2
| or (a
i
+a
i+1
+a
i+2
)
2
. For the rst quantity, to compensate for these extra
5
Semi-invariants IMOTC 2013 Moving on with moves
terms we can consider

(|a
i
| +|a
i
+a
i+1
| +|a
i
+a
i+1
+a
i+2
| +|a
i
+a
i+1
+a
i+2
+a
i+3
|). This is then
a semi-invariant. For the second quantity, it is even simpler: we just consider

a
2
i
+ (a
i
+ a
i+1
)
2
.
We give both these solutions below.
1
Solution. Let a
1
, a
2
, . . . , a
5
be the numbers at the vertices, in that order, and let s > 0 denote the
sum of these ve numbers. Let
I = I(a
1
, a
2
, . . . , a
5
) =

_
|a
i
| +|a
i
+ a
i+1
| +|a
i
+ a
i+1
+ a
i+2
| +|a
i
+ a
i+1
+ a
i+2
+ a
i+3
|
_
,
where all the sums are taken over 1 i 5 and the indices are written modulo 5. Suppose that
we perform an operation with x = a
1
, y = a
2
and z = a
3
. Then we get I

= I(a
1
+ a
2
, a
2
, a
2
+
a
3
, a
4
, a
5
) = I |s a
2
| + |s + a
2
|. Since s > 0 and a
2
< 0 it follows that I

< I. Thus I is a
positive quantity that reduces with every operation. Therefore the procedure necessarily comes to
an end.
Alternate solution. With the notation as in the above solution, let
I = I(a
1
, a
2
, . . . , a
5
) =

a
2
i
+

(a
i
+ a
i+1
)
2
.
Then I

= I(a
1
+ a
2
, a
2
, a
2
+ a
3
, a
4
, a
5
) = I + 2a
2
(s a
2
) < I. Thus the quantity I is a positive
integer that reduces with every operation and hence it follows that the procedure necessarily comes
to an end.
Problem 3.2 (USAMO 2011, Problem 2). An integer is assigned to each vertex of a regular
pentagon so that the sum of the ve integers is 2011. A turn of a solitaire game consists of
subtracting an integer m from each of the integers at two neighboring vertices and adding 2m to
the opposite vertex, which is not adjacent to either of the rst two vertices. (The amount m and
the vertices chosen can vary from turn to turn.) The game is won at a certain vertex if, after some
number of turns, that vertex has the number 2011 and the other four vertices have the number 0.
Prove that for any choice of the initial integers, there is exactly one vertex at which the game can
be won.
Discussion. This is another problem where the sum of all the numbers is an invariant. The aim
of this problem is a bit dierent in comparison with the ones we have discussed so far. In this case,
we are looking for an invariant that associates a vertex to every conguration. Since there are ve
vertices, this invariant can be thought of as an integer modulo 5, each corresponding to a vertex.
In particular, the vertices are to be numbered 0, 1, 2, 3, 4. Note that any change in the numbering
of these vertices should also change the invariant in a similar fashion. So the invariant should be a
weighted sum of the numbers.
Let us look at the trivial example where the numbers are 1, 0, 0, 0, 0. Then if the vertex to which
1 is assigned is numbered i, then the invariant should be i. Does that give any ideas?
On the other hand, consider a turn in which we add 2m to the integer at vertex v. The operation
is symmetric with respect to this vertex. If we are looking for a weighted sum that is invariant
under every turn, then the weight at v should equal to the sum of the weights at the other two
vertices (at which subtraction takes place). Suppose the weight at v is a then the sum of the weights
1
A third solution can be given by consider the semi-invariant

(ai ai+2)
2
.
6
Semi-invariants IMOTC 2013 Moving on with moves
at the other two vetices should be 2a. Intuitively, this leads to assigning weights a 2 and a + 2
at these vertices. These ideas lead to the following solution.
One more point to note is that there are two parts to the given problem: to show that there
is at most one vertex at which the game can be won; and to show that the game can in fact be
won. The latter part can be solved by trying to make the integers zero this has less to do with
invariants, and more to do with manipulations of numbers.
Solution. Let a
0
, a
1
, a
2
, a
3
, a
4
be the numbers at the vertices in that order. Let 0 I 4 be
such that I a
1
+ 2a
2
+ 3a
3
+ 4a
4
(mod 5). We claim that I is invariant under any turn. This is
because, any turn consists of changing I by mk m(k + 1) + 2m(k + 3) 0 (mod 5). If we end
up with 2011 at one vertex and zero at every other vertex then 2011 will have to be at the vertex
I. It now remains to show that we can reach this point.
We rst show that (0, 0, 0, 0, 0) can be reached from (0, 0, 5, 5, 0). This can be acheived with
the following turns:
(0, 0, 5, 5, 0) (2, 0, 1, 5, 2) (0, 2, 1, 1, 2)
(2, 2, 2, 0, 2) (0, 2, 2, 0, 4) (0, 0, 0, 0, 0) .
Now suppose that a
0
+a
1
+a
2
+a
3
+a
4
= 2011, and assume without loss of generality that I = 0.
Play a turn if necessary, and assume that a
0
= 2011. By a turn (m, k) we mean the turn where
we add 2m to a
k
and subtract m from a
k2
and a
k+2
(with indices modulo 5). Play the following
turns: (a
1
, 3) and (a
1
, 4). Our conguration then looks like (2011, 0, b
2
, b
3
, b
4
). Play the turns
(b
4
, 4) and (b
4
, 2) and (b
4
, 3) to get a conguration (2011, 0, c
3
, c
4
, 0). Since the sum of the ve
numbers is always 2011 it follows that c
3
= c
4
. Moreover, since I = 0 is an invariant it follows
that c
3
is divisible by 5. We have show that (0, 0, 5, 5, 0) can be brought to (0, 0, 0, 0, 0), so it
follows that we can reach (2011, 0, 0, 0, 0) from (2011, 0, c
3
, c
4
, 0).
Problem 3.3. There are 60 girls sitting around in a circle. One of them is initially given M
chocolates. In each move, every girl who has at least 3 chocolates gives one chocolate each to both
her neighbours. This procedure stops either if all the girls have a chocolate or if no girl has more
than 2 chocolates. Find the minimum value of M for which every girl gets a chocolate.
Discussion. One of the rst things to notice is that there are only nitely many congurations.
In such cases it is worthwhile to analyse if there is a loop. Obviously, if we there is a semi-invariant
associated with each conguration such that it (strictly) decreases (or increases) with every move
then there cannot be any loop. Suppose that there cannot be a loop, then the procedure will stop.
In that case, if M 119 then it is not hard to see (by Pigeon-Hole-Principle) that the procedure
cannot stop because of the second condition.
Note that if a girl gets a chocolate at any time, then she will have at least one chocolate there-
after. Since there is symmetry in the given problem it is therefore enough to that girl opposite
to G
0
, the girl to whom the chocolates were given initially, gets a chocolate. Also, to show that
there is no loop one can consider 59 girls sitting in a line (instead of a circle).
Another important thing to observe here is that the when a girl gives chocolates to her neigh-
bours the chocolates move away from her. This hints that the (sum of all) distances of chocolates
might be a good choice for a semi-invariant. When talking about distances, there is a choice we
need to make the choice of the origin, or the choice of the girl from whom the distances are to
be measured. In this case, the natural choice would be G
0
(or the girl opposite to her). With this
7
Semi-invariants IMOTC 2013 Moving on with moves
idea, if we naively construct the semi-invariant I(C) =

i
|a
i
| where a
i
is the distance from G
0
of
the i-th chocolate, then we realise that I(C) is monotonically (but not strictly) increasing. That is
because, if a girl gives a chocolate each to her neighbour then the semi-invariant does not increase
unless that girl is G
0
.
It is good to keep in mind that when we talk about distances it is often useful to consider the
squares of the distances rather than their absolute value. In this situation as well, if J(C) =

i
a
2
i
then it follows easily that J(C) increases strictly with every move. This is enough to conclude that
M 119.
Solution. We shall only give here half the solution. That is, we shall only prove that if M 119
then every girl gets a chocolate. The other part of the solution (which is not directly related to
any semi-invariant calculation) is left as an exercise to the reader.
We shal denote by G
0
the girl to whom the chocolates were given initially. It is clear that if a
girl gets a chocolate after some moves, then she will have a chocolate with her thereafter. Also it
is clear that if the girl G
0
sitting diagonally opposite to G
0
gets a chocolate then everyone gets a
chocolate.
Number the chocolates 1, 2, . . . , M. By a conguration, we mean a distribution of chocolates
among the girls. So in the initial conguration C
0
one girl, say G
0
, has 60 chocolates, and the rest
have none. In a conguration C, we denote by a
i
(C) the distance of the i-th chocolate from G
0
.
Here the distance between two girls is taken to be 1. Dene
J(C) =
M

i=1
a
i
(C)
2
.
If there is a move that takes C to C

, then by denition it follows that G


0
does not have any chocolate
in C. Consider a girl who had more than two chocolates in C. Let her distance from G
0
be d. Then
the change in J(C) because of her action of distribution of chocolates is 2d
2
+(d1)
2
+(d+1)
2
= 1.
This proves that J(C

) > J(C).
Suppose that M 119. If G
0
does not have a chocolate with her, then b Pigeon-Hole-Principle
it follows that at least one of the other girls has at least three chocolates, and therefore the procedure
continues (and thus increasing the semi-invariant). But the semi-invariant is bounded above by
M 29
2
, and hence it follows that all the girls get a chocolate.
Problem 3.4. There are n 1 bins B
1
, B
2
, . . . , B
n
and there are a total of n balls in them. A
move consists of one of the following: (a) if B
1
has at least two balls, then we can move one ball
to B
2
; (b) if B
n
has at least two balls, then we can move one ball to B
n1
; or (c) if B
i
has at
least two balls for some 2 i n 1, then we can move one ball to B
i1
and one to B
i+1
. Show
that starting from any initial congurations any sequence of moves will lead to the conguration
in which all the bins have exactly one ball each.
Discussion. Let us rst x some notation. For 1 i n, let a
i
denote the number of balls in
bin B
i
, so we have a
1
+ a
2
+ + a
n
= n. We can blindly try the kind of semi-invariants we have
encountered so far, for example,

a
2
i
. It is easy to see that this quantity does not satisfy any sort
of monotonicity.
Let us look at the semi-invariant that we want from a slightly dierent perspective. We want
it to measure how far we are from the desired conguration. In other words, we want to measure
how far the i-th ball is from the i-th bin. Obviously, this measure is trivial in case of the desired
8
Semi-invariants IMOTC 2013 Moving on with moves
conguration. Now let us see how we can calculate this measure. Since there are a
1
balls in the
rst bin, for i = 1, 2, . . . , a
1
, the distance of i-th ball from the i-th bin is (i 1)
2
. We have taken the
square so as to avoid the diculty in dealing with the absolute values. For i = a
1
+1, . . . , a
1
+a
2
,
the measure equals (i 2)
2
and so on. We will leave it to the reader to check that we eventually
get that the sum of all these measures is
I(a
1
, a
2
, . . . , a
n
) =
n

k=1
(s
k
k)
2
,
where s
k
= a
1
+ a
2
+ . . . + a
k
.
This semi-invariant is monotonically decreasing, but it fails to decrease strictly in one particular
case. This failure can be set right if we assign a weight.
After the solution based on the above semi-invariant idea, we shall also give an alternate solution
purely based on induction. We give this solution for two reasons. First of all, the semi-invariant
used in the solution below looks bit tricky! And secondly, the induction also provides a bit more
exibility, in the sense that the solution is same for a simple generalization stated at the end.
We want to stress that induction is more powerful than what we think, but we may have to
deal with it carefully at times. This problem is a nice example where a careful application of nested
induction leads to an alternate solution. There are three quantities, namely r, c
r
and s, on which
we apply induction, but every step is quite simple. What makes the solution a bit complicated is
the nested property.
Solution. For 1 k n, let a
k
denote the number of balls in bin B
k
and let s
k
= a
1
+a
2
+ +a
k
.
Let I(a
1
, a
2
, . . . , a
n
) =

n
k=1
(s
k
k)
2
, where 0 < < 1 is a quantity we shall choose later. We
then have
I(a
1
, a
2
, . . . , a
n
) I(a
1
1, a
2
+ 1, . . . , a
n
) = 2(a
1
) 1 > 0 ,
I(a
1
, a
2
, . . . , a
n
) I(a
1
, . . . , a
k1
+ 1, a
k
2, a
k+1
+ 1, . . . , a
n
) = 2a
k
2 2 > 0 ,
I(a
1
, a
2
, . . . , a
n
) I(a
1
, . . . , a
n1
+ 1, a
n
1) = 2(n 1) (2n 3) ,
where the last quantity is positive provided > (2n 3)/(2n 2). Thus choosing such a we
get that the value of I decreases with any move. Since there are only nitely many possible
congurations it follows that the process should terminate. It remains to show that the minimum
value of I is achieved at the desired conguration. This is true because (s
k
k)
2
(k k)
2
=
(s
k
k)(s
k
k+2k(1)) 0 for all k = 1, 2, . . . , n, and the equality holds if and only if s
k
= k.
Alternate solution. Let t
k
, for 1 k n, denote the move in (a) if k = 1, move in (b) if k = n
or the move in (c) with k = i.
Suppose that we do not have the desired conguration. Let r be the smallest index such that
B
r
has at least two balls. We shall induct on n r. The base case is when r = n. Let c
n
denote
the number of balls in B
n
. We induct again on c
n
. The base case now is when c
n
= 2, and in this
case let s < n be the unique index such that B
s
does not contain any ball. We induct (for the third
time!) on n1s. If s = n1 then applying t
n
will give us the desired conguration. If s < n1
then apply t
n
, t
n1
, . . . , t
s+1
to get a conguration in which c
n
= 2 and B
s+1
does not contain any
ball in it, and hence we are done by induction on n 1 s. This completes the base case c
n
= 2.
We now consider the (base!) case r = n and c
n
> 3. Let s be the largest index such that B
s
does not contain any ball in it. We again induct on n1 s. As before, if s = n1 then applying
9
Semi-invariants IMOTC 2013 Moving on with moves
t
n
will give us a conguration in which c
n
is smaller and we are then done by induction on c
n
.
If s < n 1 then applying t
n
, t
n1
, . . . , t
s+1
will give us a conguration in which B
s+1
does not
contain any ball, and thus we are done by induction on n 1 s. This completes the base case
r = n.
Now suppose that every conguration with r > R can be brought into the desired conguration.
Consider a conguration with r = R and let c
r
2 denote the number of balls in B
r
. We apply
induction on c
r
. Consider the base case c
r
= 2. If there is a bin B
i
, with i < R, that does not
contain any ball in it then let s denote the largest of such indices. Otherwise let s = 0. Applying
t
R
, t
R1
, . . . , t
s+1
will then result in either the desired conguration or a conguration with r > R.
This completes the proof of the base case c
r
= 2.
Now assume that c
r
> 2. Again let s be as in the case c
r
= 2. In this case, applying
t
R
, t
R1
, . . . , t
s+1
will reduce c
r
and hence we are done by induction.
The solution is now complete.
And here is a simple generalization of the previous problem.
Problem 3.5. Let n, a
1
, a
2
, . . . , a
n
be positive integers and let M = a
1
+ a
2
+ . . . + a
n
. Consider
n bins B
1
, B
2
, . . . , B
n
which contain a total of M balls in them. A move consists of one of the
following: (a) if B
1
has at least a
1
+ 1 balls, then we can move one ball to B
2
; (b) if B
n
has at
least a
n
+ 1 balls, then we can move one ball to B
n1
; or (c) if B
i
has at least a
i
+ 1 balls for
some 2 i n 1, then we can move one ball to B
i1
and one to B
i+1
. Show that starting from
any initial congurations we can make appropriate moves to get a conguration in which, for all
1 i n, B
i
contains exactly a
i
balls.
Problem 3.6 (IMO Shortlist 1996). A nite number of coins are placed on an innite row of
squares. A sequence of moves is performed as follows: at each stage a square containing more than
one coin is chosen. Two coins are taken from this square; one of them is placed on the square
immediately to the left while the other is placed on the square immediately to the right of the
chosen square. The sequence terminates if at some point there is at most one coin on each square.
Given some initial conguration, show that any legal sequence of moves will terminate.
Remark. In fact, it is also true that any legal sequence of moves will terminate after same number
of moves and in the same conguration.
Discussion. This problem is a variation of Problem 3.4. There are two dierences: we now have
an innite row of squares instead of nitely many bins; and, we also have to show that the number
of steps is same. Since there are only nite number of coins, we should be able to restrict ourselves
to a nite set of rows. For this we have to show that the coins cannot go beyond certain squares.
Intuitively, if S
k
is the left-most square with a coin in it, then the squares to the left of it can never
have all the coins in them. We shall use this in the solution below and show that only nitely many
squares need to be considered.
We notice the similarity of this problem with Problem 3.2. A move at square S
k
is symmetric
at the square. With a
k
denoting the number of coins in square S
k
, we see that

a
k
will be
an invariant, and moreover the weighted sum

ka
k
will also be an invariant (exactly like in the
solution to Problem 3.2). We are however looking for a semi-invariant. An immediate thought would
be to assign dierent weights (that almost balance each other out). Since (k1)
2
+(k+1)
2
2k
2
= 2,
the semi-invariant

k
2
a
k
should be a good choice.
10
Semi-invariants IMOTC 2013 In a dierent direction
Solution. Suppose that there are n coins. Let S
i
denote the squares with i ranging over the set of
all integers and let a
i
denote the number of coins in S
i
. A move means choosing an integer i with
a
i
2 and replacing a
i1
, a
i
, a
i+1
with a
i1
+1, a
i
2, a
i+1
+1 respectively. Suppose that S
k
is the
left-most square that has a coin in the initial conguration. Then we notice that a
k
+a
k1
+ 1
at any point of time. This is quite evident. We now prove by induction that for any i 0 we have
a
ki
+a
ki+1
+ i +1. The base case i = 0 is what we just noticed. Now consider the general
case of i > 0 (assuming the statement for i 1). If the inequality does not hold at some point of
time, then consider the move because of which this fails. This move has to happen at the square
S
ki
which will then have to have at least two coins. We then get that a
ki+1
+ a
ki+2
+ < i,
a contradiction to the induction hypothesis. We have thus proved that the coins cannot move to
the left of S
kn+1
. Similarly, we can give a bound on the right-hand side as well, so we only have
to consider nitely many squares.
Let S
1
, S
2
, . . . , S
N
be the squares to be considered. Let I(a
1
, a
2
, . . . , a
N
) =

N
k=1
k
2
a
k
. Then
I(a
1
, a
2
, . . . , a
N
) I(a
1
, . . . , a
k1
+ 1, a
k
2, a
k+1
+ 1, . . . , a
N
) = 2a
k
2 > 0 .
This proves that the any sequence of moves will terminate.
2
4 In a dierent direction
The last problem we shall consider here is of a dierent nature than the ones discussed above. We
have seen problems where our goal is to get to a nal conguration. The problem below is to prove
just the opposite that there is no nal conguration, but instead there is a repetition.
Problem 4.1 (IMO 1993, Problem 6). Let n > 1 be an integer. In a circular arrangement of n
lamps L
0
, L
1
, . . . , L
n1
, each of which can be either ON or OFF, we start with the situation where
all lamps are ON, and then carry out a sequence of steps Step
0
, Step
1
, . . .. If L
j1
(with j taken
modulo n) is ON then Step
j
changes the state of L
j
(it goes from ON to OFF, or vice versa), but
does not change the state of any other lamp. If L
j1
is OFF then Step
j
does not change anything
at all. Show that:
(a) There is a positive integer M(n) such that after M(n) steps all lamps are ON again.
(b) If n = 2
k
for some positive integer k then all the lamps are ON after n
2
1 steps.
(c) If n = 2
k
+ 1 for some positive integer k then all the lamps are ON after n
2
n + 1 steps.
Discussion. The key idea in such problems where we have to look for repetition is to consider a
backward move. If there is a unique backward move, then it follows by the niteness of the number
of congurations that they will have to repeat after a while. In terms of graph theory, this is same
as saying that if the degree of every vertex is exactly two (one for the forward move and one for
the backward move) then it comprises of disjoint cycles.
It is time to again mention two things: examples and induction! For the second part, it is quite
evident how the conguration changes if we work out couple of examples. It is then natural to
2
We note that

N
k=1
s
2
k
, with s
k
= a1 + a2 + + a
k
, is another strictly increasing semi-invariant.
11
Semi-invariants IMOTC 2013 In a dierent direction
consider a solution using induction. Working out examples will also help us see the similarities
between the congurations in the second and third part.
We shall also briey mention two alternative solutions using polynomials and generating func-
tions. These ideas dier very much from our current topic, so we shall keep the arguments to bare
minimal.
Solution. To make some of the notations simpler, we shall assume that we begin with Step
1
rather
than Step
0
. Note that this does not change any of the statements of the problem since we can
always renumber the lamps and get the exact statement as in the problem.
(a) Write (j, (a
0
, a
1
, . . . , a
n1
)) for a conguration of the lights, with each a
i
being 0 if L
i
is o
or 1 otherwise, and j indicating that we have just nished Step
j
, so the initial conguration
is (1, (1, 1, . . . , 1)). Obviously, j is written modulo n. Clearly, there are only nitely many
such congurations. This proves that the congurations repeat after a while. We note that
(j1, (a
0
, a
1
, . . . , a
j1
, a
j
+a
j1
, a
j+1
, . . . , a
n1
)) is the unique predecessor of (j, (a
1
, . . . , a
n
)),
and hence it follows that the initial conguration repeats.
(b) Suppose that n = 2
k
. We shall show the following by induction:
L
n1
is OFF after Step
n1
and remains o until Step
n
2
1
;
L
0
is ON, and all the other lamps are OFF after n
2
n steps;
all the lamps are ON after n
2
1 steps.
The statement is obvious for the base case k = 1. Suppose that k > 1 and that the statement
holds if we replace k with k 1. Let m = 2
k1
. The conguration after n 1 steps is
(1, 1010 10
. .
m
1010 10
. .
m
) .
Thanks to the rst statement in the induction, it follows that after 2(m
2
m) steps the
conguration is
(0, 1000 00
. .
m
1000 00
. .
m
) ,
and thus after 2m
2
1 steps we will have
(1, 1111 11
. .
m
0000 00
. .
m
) .
Another n steps will result in
(1, 1010 10
. .
m
0000 00
. .
m
) .
Again from the rst statement in the induction, it follows that after n
2
n steps we will have
(0, 1000 00
. .
m
0000 00
. .
m
) ,
and hence all the lights will be ON after n
2
1 steps.
12
Semi-invariants IMOTC 2013 Conclusion
(c) The conguration after two steps is (2, 1011 11) which is nothing but (0, 1111 110) but
shifted by 2. We shall consider this rotated conguration henceforth (and add 2 in the end).
After another 2
k
1 steps we get
(2
k
1, 1010 10
. .
2
k
0) .
From the previous part it follows the last two lamps remain o until we reach the conguration
(0, 100 00). We further note that it takes (2
k
1)(2
k
+ 1) = n
2
2n steps to reach this.
After another n 1 steps we will have all the lights ON, and counting the rst two steps, we
have thus performed exactly n
2
n + 1 steps.
Alternate solution. There is a clever, but less intuitive solution. Consider the polynomial P(x) =
a
0
+ a
1
x + a
2
x
2
+ + a
n1
x
n1
. Then the corresponding polynomial after Step
0
and an index
shift by 1 is Q(x) = a
n1
+ (a
0
+ a
n1
)x + a
1
x
2
+ + a
n2
x
n1
. We note that Q(x) xP(x)
(mod x
n
+ x
n1
+ 1) (where we consider all the polynomails with coecients modulo 2). The
corresponding polynomial after k steps (and with the index shifted by k) is therefore x
k
P(x)
(mod x
n
+ x
n1
+ 1). Hence it is enough to show:
(a) x
M(n)
1 (mod x
n
+ x
n1
+ 1) for some integer M(n).
(b) If n = 2
k
then x
n
2
1
1 (mod x
n
+ x
n1
+ 1).
(c) If n = 2
k
+ 1 then x
n
2
n+1
1 (mod x
n
+ x
n1
+ 1).
For part (a) we note that there are only nitely many residue classes modulo x
n
+x
n1
+1 and
hence there are integers k > l such that x
k
x
l
(mod x
n
+ x
n1
+ 1). This proves that x
kl
1
(mod x
n
+ x
n1
+ 1).
For part (b) we note that x
n
2
(x
n1
+1)
n
x
n
2
n
+1 (mod x
n
+x
n1
+1) since
_
n
k
_
is even
for all 1 k n 1. On the other hand x
n
2
= x
n
2
n
x
n
x
n
2
1
+ x
n
2
n
(mod x
n
+ x
n1
+ 1).
This proves the required equivalence.
Proof of part (c) is similar to that of part (b). In this case we have x
n
2
1
x
n
2
n
+ x
n1
(mod x
n
+ x
n1
+ 1) and then the required equivalence follows.
Alternate solution. The above solution can also be seen in a slightly dierent way using gener-
ating function. Let a
i+rn
equal 0 if the lamp L
i
is OFF after it was operated for r times (i.e., after
i + (r 1)n + 1 steps) and equal 1 otherwise. Then we have a
j+n
= a
j
+ a
j+n1
for all j 0 and
a
0
= a
1
= = a
n1
= 1. If we let G(x) =

a
j
x
j
it then follows that G(x) = 1/(1 x x
n
)
(assuming that all the coecients are considered modulo 2). This leads to a solution.
5 Conclusion
We have seen a few dierent kind of semi-invariants in this section. One should always look for
invariants, which might be at times completely useless for the solution, but will give an idea as
to what semi-invariant we should look for. It is good to keep in mind some of the standard
13
Semi-invariants IMOTC 2013 Extra problems
semi-invariants one can look for:

a
k
,

a
2
k
,

ka
k
,

k
2
a
k
,

(a
k1
+ a
k
)
2
,

s
k
. . ., and also

1/a
k
,

1/a
2
k
, . . ., or a combination of these.
Below are a few more problems. The last two problems, which can possibly be solved using
semi-invariants, are of dierent nature.
6 Extra problems
Problem 6.1. The numbers 1, 2, . . . , n are written on a blackboard. It is permitted to erase any
two numbers a and b and write the new number ab +a +b. Find with proof, the number that can
be on the blackboard after n 1 such operations?
Problem 6.2. A circle is divided into six sectors. Then the numbers 1, 0, 1, 0, 0, 0 are written into
the sectors. You may increase two neighboring numbers by 1. Is it possible to equalize all numbers
by a sequence of such steps?
Problem 6.3. Let n be a positive integer and a
1
, a
2
, . . . , a
n
positive real numbers. We put these
numbers into groups G
1
, G
2
, . . . G
r
, with r 1, with each group being non-empty. For every a
i
we
let its relative rating to be the ratio of a
i
to the sum of all the elements in the group containing
a
i
. A move consists of moving an element from one group to the other provided its relative rating
increases. Show that we can only make nitely many moves.
Problem 6.4. On each square of a chessboard is a light bulb which has two states on and o.
A move consists of choosing a square and changing the state of the bulbs in that square and in the
neighbouring squares (which share a side). Show that starting from any conguration we can make
nitely many moves to reach a point where all the bulbs are switched o.
Problem 6.5. Let a
1
, a
2
, ..., a
100
be an ordered set of numbers. At each move it is allowed to choose
any two numbers a
n
, a
m
and change them to
a
2
n
am

n
m
(
a
2
m
an
a
m
) and
a
2
m
an

m
n
(
a
2
n
am
a
n
) respectively.
Determine if it is possible, starting with the set with a
i
=
1
5
for i = 20, 40, 60, 80, 100 and a
i
= 1
otherwise, to obtain a set consisting of integers only.
Problem 6.6. We have
n(n+1)
2
stones and they are divided into a few groups. In each move we
take one stone from each group and form a new group with taken stones. Prove that after a few
moves we will get groups with 1, 2, 3, . . . , n stones (and after that position doesnt change).
Problem 6.7. Several boxes are arranged in a circle. Each box may be empty or may contain one
or several chips. A move consists of taking all the chips from some box and distributing them one
by one into subsequent boxes clockwise starting from the next box in the clockwise direction.
(a) Suppose that on each move (except for the rst one) one must take the chips from the box
where the last chip was placed on the previous move. Prove that after several moves the
initial distribution of the chips among the boxes will reappear.
(b) Now, suppose that in each move one can take the chips from any box. Is it true that for every
initial distribution of the chips you can get any possible distribution?
Problem 6.8 (IMO Shortlist 2009). Consider 2009 cards, each having one gold side and one black
side, lying on parallel on a long table. Initially all cards show their gold sides. Two player, standing
14
Semi-invariants IMOTC 2013 Extra problems
by the same long side of the table, play a game with alternating moves. Each move consists of
choosing a block of 50 consecutive cards, the leftmost of which is showing gold, and turning them
all over, so those which showed gold now show black and vice versa. The last player who can make
a legal move wins.
(a) Does the game necessarily end?
(b) Does there exist a winning strategy for the starting player?
Problem 6.9 (Korean National Mathematical Olympiad 2009, Problem 3). There are 2008 white
stones and one black stone in a row. A move means the following: select one black stone and
change the colour of its neighbouring stone(s). Find all possible initial position of the black stone
for which all the stones can be made black after nitely many moves.
Problem 6.10. There is (2n 1) (2n 1) square and for every small square there is one arrow,
up or down or right or left. A bug is on one of the small squares. It travels to a next square
following the arrow. If bug leaves the square, the arrow of the square turn

2
in counter clock wise.
Prove that this bug will be out of this big square before 2
3n1
(n 1)! 3 moves.
15

You might also like