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.


Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

Resources