Maths
Maths
Maths
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
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
|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
) > 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