2004 IMO Shortlist Problems/A2

Problem

(Mihai Bălună, Romania) An infinite sequence $a_0, a_1, a_2, \ldots$ of real numbers satisfies the condition

$\displaystyle a_n = | a_{n+1} - a_{n+2} | \qquad$ for every $n \ge 0$ ,

with $\displaystyle a_0$ and $\displaystyle a_1$ positive and distinct. Can this sequence be bounded?

This was also Problem 4 of the 2005 German Pre-TST and Problem 1 of the first 2005 black MOP test. It was Problem 3, Day 2 of the 2005 Romanian TST in the following form:

A sequence of real numbers $\displaystyle \{a_n\}_n$ is called a bs sequence if $\displaystyle a_n = |a_{n+1} - a_{n+2}|$ , for all $\displaystyle n\geq 0$ . Prove that a bs sequence is bounded if and only if the function $\displaystyle f$ given by $\displaystyle f(n,k)=a_na_k(a_n-a_k)$ , for all $\displaystyle n,k\geq 0$ is the null function.

Solution

We note that each of the $\displaystyle a_i$ must be nonnegative.

Lemma 1. If the two initial terms of the sequence are nonzero and distinct, then every term of the sequence is nonzero and no two consecutive terms are equal.

Proof. We proceed by induction; we are given a base case. If ${}a_k \neq a_{k+1}$ , then $| a_{k+1} - a_{k+2} | \neq a_{k+1}$ , so $a_{k+2} \neq 0$ . Furthermore, since $|a_{k+1} - a_{k+2}| = a_k \neq 0$ , $a_{k+1} \neq a_{k+2}$ .

Consider a sequence $\{b_i\}_{i=0}^{\infty}$ of positive reals which obeys the recursive relation

$\displaystyle b_{n+2} = |b_{n+1} - b_n |$ .

Lemma 2. $\min (b_i, b_{i+1}, b_{i+2}) \ge \min (b_{i+3}, b_{i+4}, b_{i+5})$ .

Proof. We note that if $\displaystyle b_k \le b_{k+1}$ , then $\displaystyle b_{k+2} = b_{k+1} - b_k$ and $\displaystyle b_{k+3} = b_k$ . Thus if $\displaystyle b_{i+3}, b_{i+4}, b_{i+5} > \min(b_i, b_{i+1}, b_{i+2})$ , we must have $\displaystyle b_i, b_{i+1} > b_{i+2} > b_{i+3}$ , a contradiction.

Lemma 3. Let $r = \left\lfloor \frac{b_{k-1}}{b_k} \right\rfloor$ , $j = \left\lceil \frac{3}{2}r \right\rceil$ . Then $\min (b_{k+j},b_{k+j+1},b_{k+j+2}) \le \frac{1}{2}b_{k+1}$ .

Proof. For $2i+2 \le r$ , easy induction yields $\displaystyle b_{k+3i} = b_k$ , $\displaystyle b_{k+3i+1} = b_{k-1} - (2i+1)b_k$ , $\displaystyle b_{k+3i+2} = b_{k-1} - (2i+2)b_k$ .

Now, if $\displaystyle r$ is even, we have $\displaystyle b_{k+3r/2 - 1} = b_{k-1} - b_kr$ , which is less than $\displaystyle b_k$ by the definition of $\displaystyle r$ , and $\displaystyle b_{k+3r/2} = b_k$ , $\displaystyle b_{k+3r/2 +1} = b_{3r/2} - b_{k+3r/2-1}$ , $\displaystyle b_{k+3r/2+2} = b_{k+3r/2}$ . Since $\displaystyle b_{k+3r/2+1}$ and $\displaystyle b_{k+3r/2+2}$ add to $\displaystyle b_{3r/2} = b_k$ , one of them must be at most $\frac{b_k}{2}$ , and the lemma follows.

On the other hand, if $\displaystyle r$ is odd, then set $\displaystyle s = r-1$ and we have $\displaystyle b_{k+3s/2+1} = b_{k-1} - b_kr < b_k$ , $\displaystyle b_{k+3s/2 + 2} = b_k$ , and $\displaystyle b_{k+3s/2+3} = b_{k+3s/2 + 2} - b_{k+3s/2+1}$ , so as before, at least one of $\displaystyle b_{k+3s/2+1}$ , $\displaystyle b_{k+3s/2+3}$ must be at most $\frac{b_k}{2}$ . In fact, we have $\displaystyle {} b_{k+3s/2+4}= b_{k+3s/2+1}$ , so the minimum of $\displaystyle b_{k+3s/2+3}, b_{k+3s/2+4}$ is at most $\frac{b_k}{2}$ , upholding the lemma, since in this case $\left\lceil \frac{3}{2}r \right\rceil = \frac{3}{2}s+2$ .

Now, suppose that $\{ a_i \}_{i=0}^{\infty}$ is bounded, i.e., there exists some real $\displaystyle N$ greater than each $\displaystyle a_i$ . By setting $\displaystyle b_1, b_0$ equal to $\displaystyle a_{n-1}, a_n$ , we generate the first $\displaystyle n$ of the $\displaystyle a_i$ in reverse, and from Lemma 2, we can see that $\displaystyle m = \min (a_1,a_2,a_3)$ is a lower bound of the $\displaystyle a_i$ . But by making $\displaystyle n$ greater than $\lceil \log_2 (N/m) +1 \rceil \left\lceil \frac{3}{2} \left\lfloor \frac{N}{m} \right\rfloor \right\rceil$ , by applying Lemma 3, we obtain the result $\displaystyle m \le \frac{1}{2} m$ , which is a contradiction when $\displaystyle a_0, a_1$ are distinct and greater than 0, by Lemma 1.

Now, if $\displaystyle a_na_k(a_n-a_k) = 0$ for all natural $\displaystyle n$ , all the nonzero $\displaystyle a_i$ must be equal and the sequence is bounded. On the other hand, if $\displaystyle a_{n+1}a_n(a_{n+1}-a_n) = 0$ always holds, then either $\displaystyle a_{n+1} = a_n$ and $a_{n+2} = 0$ , or one of $\displaystyle a_{n+1}, a_{n}$ is equal to zero and $\displaystyle a_{n+2}$ is equal to the other one; hence by induction, all the nonzero terms of the sequence are equal, and $\displaystyle a_na_k(a_n-a_k)$ is always equal to zero. Hence if for some $\displaystyle n, k$ , ${} a_na_k(a_n-a_k) \neq 0$ , then there exist two distinct positive consecutive terms of sequence, which is then unbounded as proven above.

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

Comment by the proposer. The following statements are equivalent for a sequence $a_0, a_1, \ldots, a_n, \ldots$ of real numbers satisfying $\displaystyle a_n = |a_{n+1} - a_{n+2}|$ for $n \ge 0$ :
i) the sequence is bounded;
ii) the function $\displaystyle f$ defined by $\displaystyle f(n,k) = a_na_k(a_n-a_k)$ , for $n,k \ge 0$ , is identically zero;
iii) the sequence is of the form $\ldots, 0,a,a,0,a,a,0,a,a, \ldots$ with $a \ge 0$ .

Resources

Page

Toolbox

Search

2004 IMO Shortlist Problems/A2

Problem

Solution

Resources