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

Latest revision as of 16:59, 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.

@@ Line 40: / Line 40: @@
 This implies the desired inequality.
-==Solution 2==
-Let <math>a_1,b_1,\dots,a_n,b_n</math> be nonnegative real numbers.  Set
-<cmath>
-S_a=\sum_{i=1}^n a_i,
-\quad
-S_b=\sum_{i=1}^n b_i,
-</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>:
-<cmath>
-P(i,j)=\alpha_i\alpha_j,
-\quad
-Q(i,j)=\beta_i\beta_j,
-\quad
-R(i,j)=\alpha_i\beta_j,
-\quad
-R^T(i,j)=\beta_i\alpha_j.
-</cmath>
-Their entropies are
-<cmath>
-H(P)
-=-\sum_{i,j}P(i,j)\log P(i,j)
-=2H(\alpha),
-</cmath>
-<cmath>
-H(Q)=2H(\beta),
-</cmath>
-<cmath>
-H(R)
-=-\sum_{i,j}R(i,j)\log R(i,j)
-=H(\alpha)+H(\beta).
-</cmath>
-Recall the overlap-total-variation identity:
-<cmath>
-\sum_x\min\{X(x),Y(x)\}
-=1-\tfrac12\|X-Y\|_1.
-</cmath>
-Hence
-<cmath>
-\sum_{i,j}\min\{P(i,j),Q(i,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\;
-\sum_{i,j}\min\{R(i,j),R^T(i,j)\}.
-</cmath>
-Finally, rescale by <math>(S_aS_b)</math> to recover the original inequality:
-<cmath>
-\sum_{i,j}\min\{a_ia_j,b_ib_j\}
-\;\le\;
-\sum_{i,j}\min\{a_ib_j,a_jb_i\}.
-</cmath>
 == 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

Page

Toolbox

Search

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

Latest revision as of 16:59, 28 June 2025

Problem

Solution

See Also