IMO Problem 1

Introduction

IMO - is an international mathematical olympiad held every year in summer in different countries. It is the most prestigious and arguably the most difficult math olympiad for high-school students. Math problems generally require original thinking and certain theoretical background. In the next series of posts I will try to present solutions and views on the problems from the point of view of past silver medalist of this olympiad,who however did not practice math olympiad problems for almost a decade.

Problem 1

Statement:

For each integer a[0] > 1, define the infinite sequence a[0], a[1], a[2], … as follows:

a[n+1] is a square root of a[n] if a[n] is a perfect square, otherwise a[n+1] = a[n] + 3

Determine all values of a[0] for which there is a number A such that a[n] = A for infinitely many values of n.

Solution:

Let’s rephrase the question (think why this is equivalent statement!):

Determine all values of a[0] such that our sequence is periodic.

Assume that a[0] is a multiple of 3, we will show that our sequence will then have a period and hence fulfill the problem statement. Indeed, assume the opposite: that there exist such values of a[0] where a generated sequence is not periodic. Among such values of a[0]’s let pick the minimum - x. Generated sequence will look as follows: x, x+3, x+6..., y, sqrt(y)..., where y is the first perfect square to occur in the sequence (it must be there because at least x*x - x is divisible by 3). We will show that:

x*x >= y or sqrt(y) < x. (1)

Denote floor(sqrt(x)) as z, (z >= 2, case z = 1 is easy to check manually). Apparently z*z <= x < (z+1)*(z+1). Since x is divisible by 3 and the sequence grows by 3 until it reaches y, the value of y has to be divisible by 3 as well, and so is its square root, i.e. 3 divides sqrt(y).. Hence, if m = z mod 3, then sqrt(y) = (z + 3 - m), but then as we established x >= (z * z) > (z + (3 - m)) = sqrt(y). Therefore we proved statement (1) from above. But that means we found a value sqrt(y) which is divisible by 3 and it does not generate a periodic sequence while being smaller than x - contradiction!. Now as we have proven if value of a[0] is divisible by 3 then our sequence is periodic.

Now assume that a[0] mod 3 = 2 and claim that our sequence is not periodic. In fact, we will prove a slightly stronger statement.

Lemma X:

if there is a member x in our sequence a[0], a[1] ..., such that x mod 3 = 2 then our sequence is not periodic

Note that a perfect square cannot have a remainder 2 modulus 3 (this is easy to check by hand), therefore starting from value of x: x, x+3, x+6, ... will all have the same remainder 2 mod 3. Which means the only operation applied to our sequence is +3 - therefore it is an infinitely growing sequence!

The only left case is if a[0] mod 3 = 1. We will show that in this case our sequence is not periodic as well. Let’s use contradiction method again and assume there is a value of a[0] such that a[0] mod 3 = 1 and the sequence is periodic. Among such value of a[0] we pick the miniumum - x. And similar to the first case assume first perfect square to appear is y (if there is none then our sequence is not periodic). If sqrt(y) mod 3 == 2 then due to Lemma X our sequence is not periodic. Therefore sqrt(y) mod 3 == 1 (none of the values in our sequence is divisible by 3 - which is easy to check). Similarly to the first case we can show that sqrt(y) < x which contradicts to the assumption that x is a minimum. Contradiction!

Answer: The only value satisfying values of a[0] are all the natural numbers divisible by 3.

Conclusion:

First step to solving the problem was rephrasing it. It is an important step, because it often helps to simplify and to understand what is actually important in the question. It also helps to see a problem under different light sometimes.

Next step was to split the problem into multiple cases. It is helpful because it gives us additional information which can be used to analyze the problem further. For instance in this problem, we split the cases by the remainder of a[0] modulo 3, because analyzing the problem knowing this information is a lot simpler.

We used mainly two tricks in this problem:

1. Contradiction method: assume that the statement false and come to the contradiction, hence proving the statement itself.

2. Pick a minimum (or maximum) satisfying the requirements. This is a good method to use in conjuction with contradiction method, if we can arrive to a smaller (bigger) value satisfying the requirements hence a giving us a contradiction.

Hope u had fun reading this!