Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2001 IMO Shortlist Problems/A5"

m (New page: == Problem == Find all positive integers <math>a_1, a_2, \ldots, a_n</math> such that <center><math>\frac {99}{100} = \frac {a_0}{a_1} + \frac {a_1}{a_2} + \cdots + \frac {a_{n - 1}}{a_n},...)
 
 
Line 5: Line 5:
  
 
== Solution ==
 
== Solution ==
−
{{solution}}
+
We claim that there is only one such sequence: <math>a_1=2, a_2=5, a_3=56, a_4=56\times 1400</math>. This works because
 +
<cmath>\frac{1}{2}+\frac{2}{5}+\frac{5}{56}+\frac{56}{56\times 1400} </cmath>
 +
<cmath>=\frac{700}{1400}+\frac{560}{1400}+\frac{125}{1400}+\frac{1}{1400}=\frac{1386}{1400}=\frac{99}{100}. </cmath>
 +
 +
It is also easy to check that <math>(a_{k+1}-1)a_{k-1} \geq a_k^2(a_k - 1)</math> for <math>k=1,2,3</math>.
 +
 +
Now we prove such a sequence is unique. We first claim that a sequence of positive integers <math>a_0, a_1,\dots, a_n</math> satisfying <math>(a_{k+1}-1)a_{k-1} \geq a_k^2(a_k - 1)</math> for <math>k = 1,2,\ldots,n-1</math> has the property that
 +
<cmath>\sum_{k=0}^{n-1}\frac{a_k}{a_{k+1}}<\frac{a_0}{a_1-1}. </cmath>
 +
We use induction on the length of the sequence.
 +
The base case is trivial (the condition guarantees that <math>a_1>1</math>). For the inductive step, notice that by the inductive hypothesis,
 +
<cmath>\sum_{k=1}^{n-1}\frac{a_k}{a_{k+1}}<\frac{a_1}{a_2-1}, </cmath>
 +
so it suffices to show
 +
<cmath>\frac{a_0}{a_1}+\frac{a_1}{a_2-1}\le \frac{a_0}{a_1-1}, </cmath>
 +
but this is equivalent to
 +
<cmath>a_0(a_1-1)(a_2-1)+a_1^2(a_1-1)\le a_0a_1(a_2-1) </cmath>
 +
<cmath>a_1^2(a_1-1)\le a_0(a_2-1), </cmath>
 +
which we know to be true.
 +
 +
Now suppose there were two sequences <math>a_1,\dots, a_n</math> and <math>a'_1,\dots, a'_m</math> 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 <math>c</math> such that <math>a_c\neq a'_c</math> (so for <math>k<c</math>, <math>a_k=a'_k</math>). Without loss of generality, let <math>a_c<a'_c</math>.
 +
 +
By our previous claim, we have that <cmath>\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},</cmath>
 +
and as a corollary, since the first <math>c-2</math> terms are equal,
 +
<cmath>\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}}, </cmath>
 +
which contradicts the fact that they are equal. So there is a unique sequence satisfying the problem conditions.
  
 
== Resources ==
 
== Resources ==

Latest revision as of 16:42, 8 August 2019

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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2001_IMO_Shortlist_Problems/A5&oldid=108503"