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. Template:Halmos

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

Resources

Page

Toolbox

Search

2006 IMO Shortlist Problems/A1

Problem

Solution

Resources