# 2006 IMO Shortlist Problems/A1

## Problem

(Estonia) A sequence of real numbers $a_0, a_1, a_2, \dots$ is defined by the formula

$a_{i+1} = \lfloor a_i \rfloor \cdot \langle a_i \rangle$ for $i \ge 0$;

here $\displaystyle a_0$ is an arbitrary real number, $\lfloor a_i \rfloor$ denotes the greatest integer not exceeding $\displaystyle a_i$, and ${} \langle a_i \rangle = a_i - \lfloor a_i \rfloor$. Prove that $\displaystyle {} a_i = a_{i+2}$ for $\displaystyle i$ sufficiently large.

## Solution

We first note that for all nonnegative integers $\displaystyle i$,

$| a_{i+1} | = | \lfloor a_i \rfloor \cdot \langle a_i \rangle | < | \lfloor a_i \rfloor |$,

so ${} \left| \lfloor a_i \rfloor \right|$ is a non-increasing function of $\displaystyle i$. We also note that if $\displaystyle a_i$ is not positive (resp. not negative), then $\displaystyle a_{i+1}$ is not positive (resp. not negative).

When $\displaystyle a_i \in [0,1]$, $\displaystyle a_{i+1} = 0$. It follows that if $\displaystyle a_0$ is nonnegative, it is enough to show that for $\displaystyle a_i > 1$, then $0 \le \lfloor a_{i+1} \rfloor < \lfloor a_i \rfloor$, for then we must eventually have $\displaystyle a_i = a_{i+1} = \dotsb = 0$. But this comes from

${} 0 \le \lfloor \lfloor a_i \rfloor \cdot \langle a_i \rangle \rfloor = \lfloor a_{i+1} \rfloor \le a_{i+1} = \lfloor a_i \rfloor \cdot \langle a_i \rangle < \lfloor a_i \rfloor$ .

We prove the result for negative $\displaystyle a_0$ by induction on $\left| \lfloor a_0 \rfloor \right|$. For our base case, $\lfloor a_0 \rfloor = -1$, we either have $\displaystyle a_0 = -1$ and $\displaystyle a_j = 0$ for positive $\displaystyle j$. For $\displaystyle -1 < a_0 < 0$, we have $a_1 = 1 - a_0, a_2 = a_0, \dots$.

Now, suppose that the statement holds for $\left| \lfloor a_0 \rfloor \right| < n$. If ever we have $|a_i| \le n-1$, then the problem reduces to a previous case. Therefore if we ever have $\langle a_i \rangle \le \frac{n-1}{n}$, then the problem reduces to a previous case. Therefore if $\displaystyle a_0$ generates a counterexample to the problem, then we must always have $a_i > \frac{n-1}{n} = 1 - \frac{1}{n}$.

Then if $\displaystyle a_0$ is a counterexample with $\lfloor a_0 \rfloor = -n$, then for nonnegative $\displaystyle i$, we must have

$\langle a_{i+1} \rangle = \left\langle -n \cdot \langle a_i \rangle \right\rangle = \left\langle -n + (n - n \cdot \langle a_i \rangle) \right\rangle = n - n\cdot \langle a_i \rangle$.

It follows by induction that

$\langle a_k \rangle = (-n)^k \langle a_0 \rangle - \sum_{i=1}^k (-n)^i$.

In particular, for all even integers $\displaystyle k$, we have

$(-n)^k \langle a_0 \rangle - \sum_{i=1}^k(-n)^i > 1 - \frac{1}{n}$
$\langle a_0 \rangle > \sum_{i=-1}^k (-n)^{i-k} = \sum_{i=0}^{k+1} (-1/n)^i$.

Since $\sum_{i=0}^{k+1}(-1/n)^i$ becomes arbitrarily close to $\frac{n}{n+1}$ as $\displaystyle k$ becomes arbitrarily large, we thus have

$\langle a_0 \rangle \ge \frac{n}{n+1}$.

But for odd integers $\displaystyle k$, the inequality is reversed, and we have

$\langle a_0 \rangle < \sum_{i=-1}^k (-n)^{i-k} = \sum_{i=0}^{k+1} (-1/n)^i$,

and similarly,

${} \langle a_0 \rangle \le \frac{n}{n+1}$.

It follows that $\displaystyle a_0$ is of the form ${} -n + \frac{n}{n+1} = \frac{-n^2}{n+1}$, for some positive integer $\displaystyle n$. But this gives us a constant sequence, which is not a counterexample. Therefore by induction, there are no negative counterexamples. Since we have already proven that the problem statement holds for nonnegative reals, we are done.