Difference between revisions of "2000 USAMO Problems/Problem 6"

(Created page with "==Problem== ''[Insert USAMO 2000 Problem 6 here]'' ==Solution== ''[Insert complete solution(s) to USAMO 2000 Problem 6 here]''")
 
(Problem)
(Tag: Replaced)
 
(5 intermediate revisions by 4 users not shown)
Line 1: Line 1:
 
==Problem==
 
==Problem==
''[Insert USAMO 2000 Problem 6 here]''
+
Let <math>a_1, b_1, a_2, b_2, \dots , a_n, b_n</math> be nonnegative real numbers. Prove that
  
 +
<cmath>\sum_{i, j = 1}^{n} \min\{a_ia_j, b_ib_j\} \le \sum_{i, j = 1}^{n} \min\{a_ib_j, a_jb_i\}.</cmath>
  
 
==Solution==
 
==Solution==
''[Insert complete solution(s) to USAMO 2000 Problem 6 here]''
+
''Credit for this solution goes to Ravi Boppana.''
 +
 
 +
'''Lemma 1:''' If <math>r_1, r_2, \ldots , r_n</math> are non-negative reals and <math>x_1, x_2, \ldots x_n</math> are reals, then
 +
 
 +
<cmath> \sum_{i, j}\min(r_{i}, r_{j}) x_{i}x_{j}\ge 0. </cmath>
 +
 
 +
'''Proof:''' Without loss of generality assume that the sequence <math>\{r_i\}</math> is increasing. For convenience, define <math>r_0=0</math>. The LHS of our inequality becomes
 +
 
 +
<cmath>\sum_{i}r_{i}x_{i}^{2}+2\sum_{i < j}r_{i}x_{i}x_{j}\, .</cmath>
 +
 
 +
This expression is equivalent to the sum
 +
 
 +
<cmath>\sum_{i}(r_{i}-r_{i-1})\biggl(\sum_{j=i}^{n}x_{j}\biggr)^{2}\, .</cmath>
 +
 
 +
Each term in the summation is non-negative, so the sum itself is non-negative. <math>\blacksquare</math>
 +
 
 +
We now define <math>r_i=\frac{\max(a_i,b_i)}{\min(a_i,b_i)}-1</math>. If <math>\min(a_i,b_i)=0</math>, then let <math>r_i</math> be any non-negative number. Define <math>x_i=\text{sgn}(a_i-b_i)\min(a_i,b_i)</math>.
 +
 
 +
'''Lemma 2:''' <math>\min(a_{i}b_{j}, a_{j}b_{i})-\min(a_{i}a_{j}, b_{i}b_{j}) =\min(r_{i}, r_{j}) x_{i}x_{j}</math>
 +
 
 +
'''Proof:''' Switching the signs of <math>a_i</math> and <math>b_i</math> preserves inequality, so we may assume that <math>a_i>b_i</math>. Similarly, we can assume that <math>a_j>b_j</math>. If <math>b_ib_j=0</math>, then both sides are zero, so we may assume that <math>b_i</math> and <math>b_j</math> are positive. We then have from the definitions of <math>r_i</math> and <math>x_i</math> that
 +
 
 +
<cmath>\begin{eqnarray*}r_{i}& = &\frac{a_{i}}{b_{i}}-1\\ r_{j}& = &\frac{a_{j}}{b_{j}}-1\\ x_{i}& = & b_{i}\\ x_{j}& = & b_{j}\, .\end{eqnarray*}</cmath>
 +
 
 +
This means that
 +
 
 +
<cmath>\begin{eqnarray*}\min(r_{i}, r_{j}) x_{i}x_{j}& = &\min\bigl(\frac{a_{i}}{b_{i}}-1,\frac{a_{j}}{b_{j}}-1\bigr) b_{i}b_{j}\\ & = &\min(a_{i}b_{j}, a_{j}b_{i})-b_{i}b_{j}\\ & = &\min(a_{i}b_{j}, a_{j}b_{i})-\min(a_{i}a_{j}, b_{i}b_{j})\, .\end{eqnarray*}</cmath>
 +
 
 +
This concludes the proof of Lemma 2. <math>\blacksquare</math>
 +
 
 +
We can then apply Lemma 2 and Lemma 1 in order to get that
 +
 
 +
<cmath>\begin{eqnarray*}\sum_{i,j}\min(a_{i}b_{j}, a_{j}b_{i})-\sum_{i, j}\min(a_{i}a_{j}, b_{i}b_{j}) & = &\sum_{i, j}\left[\min(a_{i}b_{j}, a_{j}b_{i})-\min(a_{i}a_{j}, b_{i}b_{j})\right]\\ & = &\sum_{i, j}\min(r_{i}, r_{j}) x_{i}x_{j}\\ &\ge & 0\, .\end{eqnarray*}</cmath>
 +
 
 +
This implies the desired inequality.
 +
 
 +
== See Also ==
 +
{{USAMO newbox|year=2000|num-b=5|after=Last Question}}
 +
 
 +
[[Category:Olympiad Algebra Problems]]
 +
[[Category:Olympiad Inequality Problems]]
 +
{{MAA Notice}}

Latest revision as of 15:08, 15 July 2021

Problem

Let $a_1, b_1, a_2, b_2, \dots , a_n, b_n$ be nonnegative real numbers. Prove that

\[\sum_{i, j = 1}^{n} \min\{a_ia_j, b_ib_j\} \le \sum_{i, j = 1}^{n} \min\{a_ib_j, a_jb_i\}.\]

Solution

Credit for this solution goes to Ravi Boppana.

Lemma 1: If $r_1, r_2, \ldots , r_n$ are non-negative reals and $x_1, x_2, \ldots x_n$ are reals, then

\[\sum_{i, j}\min(r_{i}, r_{j}) x_{i}x_{j}\ge 0.\]

Proof: Without loss of generality assume that the sequence $\{r_i\}$ is increasing. For convenience, define $r_0=0$. The LHS of our inequality becomes

\[\sum_{i}r_{i}x_{i}^{2}+2\sum_{i < j}r_{i}x_{i}x_{j}\, .\]

This expression is equivalent to the sum

\[\sum_{i}(r_{i}-r_{i-1})\biggl(\sum_{j=i}^{n}x_{j}\biggr)^{2}\, .\]

Each term in the summation is non-negative, so the sum itself is non-negative. $\blacksquare$

We now define $r_i=\frac{\max(a_i,b_i)}{\min(a_i,b_i)}-1$. If $\min(a_i,b_i)=0$, then let $r_i$ be any non-negative number. Define $x_i=\text{sgn}(a_i-b_i)\min(a_i,b_i)$.

Lemma 2: $\min(a_{i}b_{j}, a_{j}b_{i})-\min(a_{i}a_{j}, b_{i}b_{j}) =\min(r_{i}, r_{j}) x_{i}x_{j}$

Proof: Switching the signs of $a_i$ and $b_i$ preserves inequality, so we may assume that $a_i>b_i$. Similarly, we can assume that $a_j>b_j$. If $b_ib_j=0$, then both sides are zero, so we may assume that $b_i$ and $b_j$ are positive. We then have from the definitions of $r_i$ and $x_i$ that

\begin{eqnarray*}r_{i}& = &\frac{a_{i}}{b_{i}}-1\\ r_{j}& = &\frac{a_{j}}{b_{j}}-1\\ x_{i}& = & b_{i}\\ x_{j}& = & b_{j}\, .\end{eqnarray*}

This means that

\begin{eqnarray*}\min(r_{i}, r_{j}) x_{i}x_{j}& = &\min\bigl(\frac{a_{i}}{b_{i}}-1,\frac{a_{j}}{b_{j}}-1\bigr) b_{i}b_{j}\\ & = &\min(a_{i}b_{j}, a_{j}b_{i})-b_{i}b_{j}\\ & = &\min(a_{i}b_{j}, a_{j}b_{i})-\min(a_{i}a_{j}, b_{i}b_{j})\, .\end{eqnarray*}

This concludes the proof of Lemma 2. $\blacksquare$

We can then apply Lemma 2 and Lemma 1 in order to get that

\begin{eqnarray*}\sum_{i,j}\min(a_{i}b_{j}, a_{j}b_{i})-\sum_{i, j}\min(a_{i}a_{j}, b_{i}b_{j}) & = &\sum_{i, j}\left[\min(a_{i}b_{j}, a_{j}b_{i})-\min(a_{i}a_{j}, b_{i}b_{j})\right]\\ & = &\sum_{i, j}\min(r_{i}, r_{j}) x_{i}x_{j}\\ &\ge & 0\, .\end{eqnarray*}

This implies the desired inequality.

See Also

2000 USAMO (ProblemsResources)
Preceded by
Problem 5
Followed by
Last Question
1 2 3 4 5 6
All USAMO Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png