Kvant Math Problem 244
The desired inequality can be rewritten as
Verified: no
Verdicts: SKIP + SKIP
Solve time: 6m36s
Source on kvant.digital
Problem
Two sets of $n$ real numbers are given: $a_1$, $a_2$, $\ldots$, $a_n$ and $b_1$, $b_2$, $\ldots$, $b_n$. Prove that if at least one of the following two conditions holds:
- $a_i\lt a_j$ implies $b_i\le b_j$;
- $a_i\lt a\lt a_j$, where $a=\dfrac{a_1+a_2+\ldots+a_n}n$, implies $b_i\le b_j$;
then the inequality $$n(a_1b_1+a_2b_2+\ldots+a_nb_n)\ge(a_1+a_2+\ldots+a_n)(b_1+b_2+\ldots+b_n).$$ holds.
A. Grigoryan, 10th-grade student (Baku)
Exploration
The desired inequality can be rewritten as
$$\sum_{i=1}^n (a_i-a)(b_i-\bar b)\ge 0,$$
where
$$a=\frac1n\sum_{i=1}^n a_i,\qquad \bar b=\frac1n\sum_{i=1}^n b_i.$$
Since $\sum (a_i-a)=0$, this is equivalent to
$$\sum_{i=1}^n (a_i-a)b_i\ge 0.$$
The first condition says that the sequence $b_i$ is nondecreasing when the $a_i$ are arranged in increasing order. This is exactly the setting of Chebyshev's sum inequality or the rearrangement principle, so the inequality should follow from a covariance argument.
The second condition is weaker. It compares only pairs $a_i<a<a_j$. Let
$$x_i=a_i-a.$$
Then $\sum x_i=0$. The condition says that whenever $x_i<0<x_j$, one has $b_i\le b_j$.
Writing
$$\sum x_i b_i = \sum_{x_i>0}x_i b_i-\sum_{x_i<0}(-x_i)b_i,$$
suggests pairing positive and negative masses. Since the total positive mass equals the total negative mass,
$$\sum_{x_i>0}x_i = \sum_{x_i<0}(-x_i),$$
it should be possible to represent the difference as a weighted sum of terms $b_j-b_i$ with $x_i<0<x_j$. Every such term is nonnegative by condition 2.
The delicate point is to justify rigorously that such a decomposition exists.
A convenient way is to define
$$\alpha_i=-x_i>0 \quad (x_i<0),\qquad \beta_j=x_j>0 \quad (x_j>0).$$
Since $\sum\alpha_i=\sum\beta_j$, there exist nonnegative numbers $m_{ij}$ such that
$$\sum_j m_{ij}=\alpha_i,\qquad \sum_i m_{ij}=\beta_j.$$
Then
$$\sum x_i b_i = \sum_{i,j}m_{ij}(b_j-b_i),$$
which is nonnegative under condition 2.
Condition 1 should imply condition 2 immediately, because $a_i<a<a_j$ certainly gives $a_i<a_j$.
Problem Understanding
We are given two collections of real numbers $a_1,\dots,a_n$ and $b_1,\dots,b_n$. We must prove
$$n\sum_{i=1}^n a_i b_i \ge \left(\sum_{i=1}^n a_i\right)\left(\sum_{i=1}^n b_i\right)$$
under either of two hypotheses. The second hypothesis states that whenever one $a_i$ lies below the average value
$$a=\frac{a_1+\cdots+a_n}{n}$$
and another lies above it, the corresponding $b$-values satisfy the same order relation.
This is a Type B problem. The task is to prove the stated inequality.
The core difficulty is that condition 2 does not impose any ordering among numbers on the same side of the mean. One must exploit only the comparison between indices below the mean and indices above the mean.
Proof Architecture
First, rewrite the target inequality as $\sum_{i=1}^n (a_i-a)b_i\ge0$, where $a$ is the arithmetic mean of the $a_i$.
Second, show that condition 1 implies condition 2, so it suffices to prove the inequality assuming condition 2.
Third, partition the indices into those with $a_i<a$ and those with $a_i>a$, and define positive quantities $\alpha_i=a-a_i$ and $\beta_j=a_j-a$.
Fourth, prove that the total negative deviation equals the total positive deviation, namely $\sum\alpha_i=\sum\beta_j$.
Fifth, prove the existence of nonnegative coefficients $m_{ij}$ whose row sums are $\alpha_i$ and whose column sums are $\beta_j$.
Sixth, express $\sum (a_i-a)b_i$ as $\sum m_{ij}(b_j-b_i)$.
Finally, use condition 2 to show every term $b_j-b_i$ in this representation is nonnegative.
The lemma most likely to fail under scrutiny is the decomposition by the coefficients $m_{ij}$, since it is the step that converts the algebraic expression into a sum of manifestly nonnegative terms.
Solution
Let
$$a=\frac{a_1+\cdots+a_n}{n}.$$
The required inequality is
$$n\sum_{i=1}^n a_i b_i \ge \left(\sum_{i=1}^n a_i\right)\left(\sum_{i=1}^n b_i\right).$$
Since $\sum_{i=1}^n a_i=na$, this is equivalent to
$$\sum_{i=1}^n a_i b_i \ge a\sum_{i=1}^n b_i,$$
or
$$\sum_{i=1}^n (a_i-a)b_i\ge0.$$
Condition 1 implies condition 2, because from
$$a_i<a<a_j$$
one obtains $a_i<a_j$, hence $b_i\le b_j$ by condition 1.
Consequently it is enough to prove the inequality assuming condition 2.
Let
$$L={i:a_i<a},\qquad R={j:a_j>a}.$$
For $i\in L$ define
$$\alpha_i=a-a_i>0,$$
and for $j\in R$ define
$$\beta_j=a_j-a>0.$$
Since
$$\sum_{k=1}^n (a_k-a)=0,$$
we have
$$\sum_{j\in R}\beta_j = \sum_{i\in L}\alpha_i.$$
Denote this common value by $S$.
There exist nonnegative numbers $m_{ij}$, $i\in L$, $j\in R$, such that
$$\sum_{j\in R}m_{ij}=\alpha_i \quad (i\in L),$$
and
$$\sum_{i\in L}m_{ij}=\beta_j \quad (j\in R).$$
To construct them, one may successively transfer mass from the quantities $\alpha_i$ to the quantities $\beta_j$. At each step choose indices with remaining positive amounts and transfer the smaller of the two remaining amounts. The process terminates because each transfer reduces at least one remaining amount to zero. The equality of the total masses $S$ guarantees that all row and column requirements are eventually satisfied.
Using these coefficients,
$$\begin{aligned} \sum_{k=1}^n (a_k-a)b_k &= \sum_{j\in R}\beta_j b_j - \sum_{i\in L}\alpha_i b_i \ &= \sum_{j\in R}\left(\sum_{i\in L}m_{ij}\right)b_j - \sum_{i\in L}\left(\sum_{j\in R}m_{ij}\right)b_i \ &= \sum_{i\in L}\sum_{j\in R}m_{ij}(b_j-b_i). \end{aligned}$$
For every pair $i\in L$, $j\in R$ we have
$$a_i<a<a_j.$$
Condition 2 therefore yields
$$b_i\le b_j.$$
Hence every factor $b_j-b_i$ is nonnegative. Since also $m_{ij}\ge0$, each term
$$m_{ij}(b_j-b_i)$$
is nonnegative. Therefore
$$\sum_{k=1}^n (a_k-a)b_k\ge0.$$
This is equivalent to
$$n\sum_{k=1}^n a_k b_k \ge \left(\sum_{k=1}^n a_k\right) \left(\sum_{k=1}^n b_k\right).$$
This completes the proof.
∎
Verification of Key Steps
The first delicate step is the passage from the original inequality to
$$\sum_{i=1}^n (a_i-a)b_i\ge0.$$
Starting from
$$n\sum a_i b_i\ge\left(\sum a_i\right)\left(\sum b_i\right),$$
and using $\sum a_i=na$, division by $n$ gives
$$\sum a_i b_i\ge a\sum b_i.$$
Subtracting the right-hand side yields exactly
$$\sum (a_i-a)b_i\ge0.$$
No additional assumptions are used.
The second delicate step is the existence of the numbers $m_{ij}$. The only required input is
$$\sum_{i\in L}\alpha_i=\sum_{j\in R}\beta_j.$$
The iterative transfer procedure never creates negative quantities. Each transfer eliminates at least one positive remainder, so after finitely many steps all remainders vanish. The resulting coefficients satisfy the prescribed row and column sums.
The third delicate step is the identity
$$\sum_{k=1}^n (a_k-a)b_k = \sum_{i\in L}\sum_{j\in R}m_{ij}(b_j-b_i).$$
Expanding the right-hand side gives
$$\sum_{j\in R} \left(\sum_{i\in L}m_{ij}\right)b_j - \sum_{i\in L} \left(\sum_{j\in R}m_{ij}\right)b_i.$$
Replacing the inner sums by $\beta_j$ and $\alpha_i$ recovers
$$\sum_{j\in R}\beta_j b_j - \sum_{i\in L}\alpha_i b_i,$$
which equals $\sum (a_k-a)b_k$ by definition of $\alpha_i$ and $\beta_j$.
Alternative Approaches
Under condition 1, one may sort the indices by increasing $a_i$. The corresponding sequence $b_i$ is then also nondecreasing. Chebyshev's sum inequality gives
$$\frac1n\sum a_i b_i \ge \left(\frac1n\sum a_i\right) \left(\frac1n\sum b_i\right),$$
which is exactly the desired result. This proof is short but uses a classical inequality as a black box.
The argument presented above proves the stronger statement based solely on condition 2. It reveals the structure behind the inequality: after centering the $a_i$ at their mean, the expression becomes a weighted sum of differences $b_j-b_i$ between indices lying on opposite sides of the mean. Every such difference is nonnegative by hypothesis, so the conclusion follows directly. This approach explains why the weaker condition 2 is already sufficient.