Difference between revisions of "2002 IMO Shortlist Problems/A2"
m |
|||
(One intermediate revision by one other user not shown) | |||
Line 1: | Line 1: | ||
== Problem == | == Problem == | ||
− | Let <math> | + | Let <math>a_1, a_b, \ldots </math> be an infinite sequence of real numbers, for which there exists a real number <math>c </math> with <math>0 \le a_i \le c </math> for all <math>i </math>, such that |
<center> | <center> | ||
Line 9: | Line 9: | ||
</center> | </center> | ||
− | Prove that <math> | + | Prove that <math>c \ge 1 </math>. |
== Solutions == | == Solutions == | ||
Line 15: | Line 15: | ||
=== Solution 1 === | === Solution 1 === | ||
− | For some fixed value of <math> | + | For some fixed value of <math>n </math>, let <math>\sigma </math> be the [[permutation]] of the first <math>n </math> natural numbers such that <math> a_{\sigma(1)} , \ldots a_{\sigma(n)} </math> is an increasing sequence. Then we have |
<center> | <center> | ||
<math> | <math> | ||
\begin{matrix} | \begin{matrix} | ||
− | a_{\sigma(n)} - a_{\sigma(1)} &= | + | a_{\sigma(n)} - a_{\sigma(1)} &=\sum_{i=1}^{n-1} \left| a_{\sigma(i+1)} - a_{\sigma(i)} \right| \qquad \quad \\ |
− | &\ge | + | &\ge\sum_{i=1}^{n-1} \frac{1}{\sigma(i+1) + \sigma(i)} \qquad (*) |
\end{matrix} | \end{matrix} | ||
</math> | </math> | ||
Line 31: | Line 31: | ||
<math> | <math> | ||
\begin{matrix} | \begin{matrix} | ||
− | + | \left( \sum_{i=1}^{n-1} \frac{1}{\sigma(i+1) + \sigma(i)} \right) \left( \sum_{i=1}^{n-1} \sigma(i+1) + \sigma(i) \right) & \ge & (n-1)^2 \qquad \qquad \qquad \\ | |
− | + | \qquad \qquad \qquad \qquad \qquad \sum_{i=1}^{n-1} \frac{1}{\sigma(i+1) + \sigma(i)} & \ge &\frac{(n-1)^2}{2 \sum_{i=1}^{n-1} (\sigma_{i}) - \sigma(1) - \sigma(n)} \\ | |
− | & \ge & | + | & \ge &\frac{(n-1)^2}{n(n+1) -3} \qquad \qquad \\ |
− | & \ge & | + | & \ge &\frac{n-1}{n+3} . \qquad \qquad \qquad \quad |
\end{matrix} | \end{matrix} | ||
</math> | </math> | ||
</center> | </center> | ||
− | Thus for all <math> | + | Thus for all <math>n </math>, we must have |
<center> | <center> | ||
Line 47: | Line 47: | ||
</center> | </center> | ||
− | and therefore <math> | + | and therefore <math>c </math> must be at least 1, Q.E.D. |
=== Solution 2 === | === Solution 2 === | ||
− | We proceed to <math> | + | We proceed to <math>(*) </math> as in Solution 1. We now note that by the [[RMS-AM-GM-HM | AM-HM Inequality]], |
<center> | <center> | ||
<math> | <math> | ||
\begin{matrix} | \begin{matrix} | ||
− | + | \sum_{i=1}^{n-1} \frac{1}{\sigma(i+1) + \sigma(i)} & \ge &\frac{(n-1)^2}{\sum_{i=1}^{n-1} \left[ \sigma(i+1) + \sigma(i) \right] } \qquad \qquad \qquad \\ | |
− | & > & | + | & > &\frac{(n-1)^2}{\sum_{i=1}^{n-1} \left[ \sigma(i+1) + \sigma(i) \right] + \sigma(n) + \sigma(1) } \\ |
− | & = & | + | & = &\frac{(n-1)^2}{n(n+1)} . \qquad \qquad \qquad \qquad \qquad \quad |
\end{matrix} | \end{matrix} | ||
</math> | </math> | ||
</center> | </center> | ||
− | Thus for any <math> | + | Thus for any <math>n </math>, we have two <math>a_i </math> that differ by more than <math> \frac{(n-1)^2}{n(n+1)} </math>. But this becomes arbitrarily close to 1 as <math>n </math> becomes arbitrarily large. Hence if we had <math>c < 1 </math>, then we could obtain a contradiction, so we conclude that <math>c \ge 1 </math>, Q.E.D. |
{{alternate solutions}} | {{alternate solutions}} | ||
Line 69: | Line 69: | ||
== Notes == | == Notes == | ||
− | The chief difficulty of this problem seems to be obtaining <math> | + | The chief difficulty of this problem seems to be obtaining <math>(*) </math>; once this result has been obtained, there are many ways to conclude. |
== Resources == | == Resources == | ||
* [[2002 IMO Shortlist Problems]] | * [[2002 IMO Shortlist Problems]] | ||
+ | * [http://www.artofproblemsolving.com/Forum/viewtopic.php?t=17331 Discussion on AoPS/MathLinks] | ||
[[Category:Olympiad Algebra Problems]] | [[Category:Olympiad Algebra Problems]] | ||
+ | [[Category:Olympiad Inequality Problems]] |
Latest revision as of 17:58, 20 August 2008
Problem
Let be an infinite sequence of real numbers, for which there exists a real number
with
for all
, such that
Prove that .
Solutions
Solution 1
For some fixed value of , let
be the permutation of the first
natural numbers such that
is an increasing sequence. Then we have
Now, by the Cauchy-Schwarz Inequality, we have
Thus for all , we must have
and therefore must be at least 1, Q.E.D.
Solution 2
We proceed to as in Solution 1. We now note that by the AM-HM Inequality,
Thus for any , we have two
that differ by more than
. But this becomes arbitrarily close to 1 as
becomes arbitrarily large. Hence if we had
, then we could obtain a contradiction, so we conclude that
, Q.E.D.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.
Notes
The chief difficulty of this problem seems to be obtaining ; once this result has been obtained, there are many ways to conclude.