2001 IMO Shortlist Problems/A5

Problem

Find all positive integers $a_1, a_2, \ldots, a_n$ such that

$\frac {99}{100} = \frac {a_0}{a_1} + \frac {a_1}{a_2} + \cdots + \frac {a_{n - 1}}{a_n},$

where $a_0 = 1$ and $(a_{k + 1} - 1)a_{k - 1} \geq a_k^2(a_k - 1)$ for $k = 1,2,\ldots,n - 1$ .

Solution

We claim that there is only one such sequence: $a_1=2, a_2=5, a_3=56, a_4=56\times 1400$ . This works because $\frac{1}{2}+\frac{2}{5}+\frac{5}{56}+\frac{56}{56\times 1400}$ $=\frac{700}{1400}+\frac{560}{1400}+\frac{125}{1400}+\frac{1}{1400}=\frac{1386}{1400}=\frac{99}{100}.$

It is also easy to check that $(a_{k+1}-1)a_{k-1} \geq a_k^2(a_k - 1)$ for $k=1,2,3$ .

Now we prove such a sequence is unique. We first claim that a sequence of positive integers $a_0, a_1,\dots, a_n$ satisfying $(a_{k+1}-1)a_{k-1} \geq a_k^2(a_k - 1)$ for $k = 1,2,\ldots,n-1$ has the property that $\sum_{k=0}^{n-1}\frac{a_k}{a_{k+1}}<\frac{a_0}{a_1-1}.$ We use induction on the length of the sequence. The base case is trivial (the condition guarantees that $a_1>1$ ). For the inductive step, notice that by the inductive hypothesis, $\sum_{k=1}^{n-1}\frac{a_k}{a_{k+1}}<\frac{a_1}{a_2-1},$ so it suffices to show $\frac{a_0}{a_1}+\frac{a_1}{a_2-1}\le \frac{a_0}{a_1-1},$ but this is equivalent to $a_0(a_1-1)(a_2-1)+a_1^2(a_1-1)\le a_0a_1(a_2-1)$ $a_1^2(a_1-1)\le a_0(a_2-1),$ which we know to be true.

Now suppose there were two sequences $a_1,\dots, a_n$ and $a'_1,\dots, a'_m$ that satisfied the conditions in the problem. Clearly one cannot be a subsequence of the other, or else the longer one will obviously have a larger sum. So there exists a smallest integer $c$ such that $a_c\neq a'_c$ (so for $k<c$ , $a_k=a'_k$ ). Without loss of generality, let $a_c<a'_c$ .

By our previous claim, we have that $\sum_{k=c-1}^{n-1}\frac{a'_k}{a'_{k+1}}<\frac{a'_{c-1}}{a'_c-1}=\frac{a_{c-1}}{a'_c-1}\le\frac{a_{c-1}}{a_c},$ and as a corollary, since the first $c-2$ terms are equal, $\sum_{k=1}^{n-1}\frac{a'_k}{a'_{k+1}}<\sum_{k=1}^{c-1}\frac{a_k}{a_{k+1}}\le \sum_{k=1}^{m-1}\frac{a_k}{a_{k+1}},$ which contradicts the fact that they are equal. So there is a unique sequence satisfying the problem conditions.

Resources

Page

Toolbox

Search

2001 IMO Shortlist Problems/A5

Problem

Solution

Resources