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 "2000 USAMO Problems/Problem 6"

(→‎Solution 2)
(→‎Solution 2)
Line 43: Line 43:
 
==Solution 2==
 
==Solution 2==
  
−
Let <math>a_1,b_1,\dots,a_n,b_n</math> be nonnegative real numbers.  Set
+
Let <math>a_1,\dots,a_n,b_1,\dots,b_n\ge0</math>.  Fix <math>\tau>0</math> and define
 
<cmath>
 
<cmath>
−
S_a=\sum_{i=1}^n a_i,
+
\mathop{\mathrm{softmin}}_\tau(x,y)
−
\quad
+
:=-\tau\ln\!\bigl(e^{-x/\tau}+e^{-y/\tau}\bigr)
−
S_b=\sum_{i=1}^n b_i,
+
\;=\;
 +
\min_{p_1+p_2=1}\Bigl\{p_1x+p_2y+\tau\bigl(-p_1\ln p_1-p_2\ln p_2\bigr)\Bigr\}.
 
</cmath>
 
</cmath>
−
and define normalized distributions
 
−
<cmath>
 
−
\alpha_i=\frac{a_i}{S_a},
 
−
\quad
 
−
\beta_i=\frac{b_i}{S_b},
 
−
</cmath>
 
−
so that <math>\sum_i\alpha_i=\sum_i\beta_i=1</math>.
 
  
−
Consider the four joint distributions on <math>[n]\times[n]</math>:
+
For each pair <math>(i,j)</math> let
 
<cmath>
 
<cmath>
−
P(i,j)=\alpha_i\alpha_j,
+
p_{ij}^*=(p_{ij}^{(1)},p_{ij}^{(2)})
−
\quad
+
</cmath>
−
Q(i,j)=\beta_i\beta_j,
+
be the minimizer in the variational formula for
−
\quad
+
<math>\mathop{\mathrm{softmin}}_\tau(a_i b_j,\,a_j b_i)</math>.  Then by definition
−
R(i,j)=\alpha_i\beta_j,
 
−
\quad
 
−
R^T(i,j)=\beta_i\alpha_j.
 
−
</cmath>
 
−
 
 
−
Their entropies are
 
 
<cmath>
 
<cmath>
−
H(P)
+
\mathop{\mathrm{softmin}}_\tau(a_i b_j,\,a_j b_i)
−
=-\sum_{i,j}P(i,j)\log P(i,j)
+
=p_{ij}^{(1)}\,a_i b_j+p_{ij}^{(2)}\,a_j b_i
−
=2H(\alpha),
+
+\tau H\bigl(p_{ij}^*\bigr),
 
</cmath>
 
</cmath>
 +
while for the “pure’’ pair we have the upper bound
 
<cmath>
 
<cmath>
−
H(Q)=2H(\beta),
+
\mathop{\mathrm{softmin}}_\tau(a_i a_j,\,b_i b_j)
 +
\;\le\;
 +
p_{ij}^{(1)}\,a_i a_j+p_{ij}^{(2)}\,b_i b_j
 +
+\tau H\bigl(p_{ij}^*\bigr).
 
</cmath>
 
</cmath>
 +
Hence term‐by‐term
 
<cmath>
 
<cmath>
−
H(R)
+
\mathop{\mathrm{softmin}}_\tau(a_i a_j,b_i b_j)
−
=-\sum_{i,j}R(i,j)\log R(i,j)
+
\;\le\;
−
=H(\alpha)+H(\beta).
+
\mathop{\mathrm{softmin}}_\tau(a_i b_j,a_j b_i),
−
</cmath>
 
−
 
 
−
Obtaining the total variation distance:
 
−
<cmath>
 
−
\sum_x\min\{X(x),Y(x)\}
 
−
=1-\tfrac12\|X-Y\|_1.
 
 
</cmath>
 
</cmath>
−
Hence
+
and summing over <math>i,j=1,\dots,n</math> gives
 
<cmath>
 
<cmath>
−
\sum_{i,j}\min\{P(i,j),Q(i,j)\}
+
\sum_{i,j}\mathop{\mathrm{softmin}}_\tau(a_i a_j,b_i b_j)
−
=1-\tfrac12\|P-Q\|_1,
 
−
</cmath>
 
−
<cmath>
 
−
\sum_{i,j}\min\{R(i,j),R^T(i,j)\}
 
−
=1-\tfrac12\|R-R^T\|_1.
 
−
</cmath>
 
−
 
 
−
Since <math>H(R)\ge\max\{H(P),H(Q)\}</math>, one shows (e.g. via Pinsker’s inequality or coupling arguments) that
 
−
<cmath>
 
−
\|P-Q\|_1\;\ge\;\|R-R^T\|_1.
 
−
</cmath>
 
−
Therefore
 
−
<cmath>
 
−
\sum_{i,j}\min\{P(i,j),Q(i,j)\}
 
 
\;\le\;
 
\;\le\;
−
\sum_{i,j}\min\{R(i,j),R^T(i,j)\}.
+
\sum_{i,j}\mathop{\mathrm{softmin}}_\tau(a_i b_j,a_j b_i).
 
</cmath>
 
</cmath>
−
 
+
Finally let <math>\tau\to0^+</math>; since
−
Finally, rescale by <math>(S_aS_b)</math> to recover the original inequality:
+
<math>\mathop{\mathrm{softmin}}_\tau(x,y)\to\min(x,y)</math>, we recover
 
<cmath>
 
<cmath>
−
\sum_{i,j}\min\{a_ia_j,b_ib_j\}
+
\sum_{i,j}\min(a_i a_j,b_i b_j)
 
\;\le\;
 
\;\le\;
−
\sum_{i,j}\min\{a_ib_j,a_jb_i\}.
+
\sum_{i,j}\min(a_i b_j,a_j b_i),
 
</cmath>
 
</cmath>
 +
as required.
  
 
== See Also ==
 
== See Also ==

Revision as of 16:47, 28 June 2025

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.

Solution 2

Let $a_1,\dots,a_n,b_1,\dots,b_n\ge0$. Fix $\tau>0$ and define \[\mathop{\mathrm{softmin}}_\tau(x,y) :=-\tau\ln\!\bigl(e^{-x/\tau}+e^{-y/\tau}\bigr) \;=\; \min_{p_1+p_2=1}\Bigl\{p_1x+p_2y+\tau\bigl(-p_1\ln p_1-p_2\ln p_2\bigr)\Bigr\}.\]

For each pair $(i,j)$ let \[p_{ij}^*=(p_{ij}^{(1)},p_{ij}^{(2)})\] be the minimizer in the variational formula for $\mathop{\mathrm{softmin}}_\tau(a_i b_j,\,a_j b_i)$. Then by definition \[\mathop{\mathrm{softmin}}_\tau(a_i b_j,\,a_j b_i) =p_{ij}^{(1)}\,a_i b_j+p_{ij}^{(2)}\,a_j b_i +\tau H\bigl(p_{ij}^*\bigr),\] while for the “pure’’ pair we have the upper bound \[\mathop{\mathrm{softmin}}_\tau(a_i a_j,\,b_i b_j) \;\le\; p_{ij}^{(1)}\,a_i a_j+p_{ij}^{(2)}\,b_i b_j +\tau H\bigl(p_{ij}^*\bigr).\] Hence term‐by‐term \[\mathop{\mathrm{softmin}}_\tau(a_i a_j,b_i b_j) \;\le\; \mathop{\mathrm{softmin}}_\tau(a_i b_j,a_j b_i),\] and summing over $i,j=1,\dots,n$ gives \[\sum_{i,j}\mathop{\mathrm{softmin}}_\tau(a_i a_j,b_i b_j) \;\le\; \sum_{i,j}\mathop{\mathrm{softmin}}_\tau(a_i b_j,a_j b_i).\] Finally let $\tau\to0^+$; since $\mathop{\mathrm{softmin}}_\tau(x,y)\to\min(x,y)$, we recover \[\sum_{i,j}\min(a_i a_j,b_i b_j) \;\le\; \sum_{i,j}\min(a_i b_j,a_j b_i),\] as required.

See Also

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

These problems are copyrighted © by the Mathematical Association of America, as part of the American Mathematics Competitions. AMC Logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2000_USAMO_Problems/Problem_6&oldid=252704"