IMO China National Team Selection Test

Proof. Consider the set of points $\mathcal{P} = \{(i_0, j_0), (i_1, j_1), \dots, (i_{m+n}, j_{m+n})\}$ as a "monotone path" from $(0, 0)$ to $(m, n)$ if $(i_0, j_0) = (0, 0)$, $(i_{m+n}, j_{m+n}) = (m, n)$, and for every index $0 \le k < m + n$, we have
$$(i_{k+1}, j_{k+1}) \in \{(i_k + 1, j_k), (i_k, j_k + 1)\}.$$
Given two non-negative decreasing sequences $u_0 \ge u_1 \ge \dots \ge u_m$ and $v_0 \ge v_1 \ge \dots \ge v_n$, define the weight of the monotone path $\mathcal{P}$ as
$$W(\mathcal{P}) = \sum_{k=0}^{m+n} u_{i_k} v_{j_k}.$$
Lemma: There exists a monotone path $\mathcal{P}$ such that
$$W(\mathcal{P}) \ge \frac{m+n+1}{(m+1)(n+1)} \left(\sum_{i=0}^m u_i\right) \left(\sum_{j=0}^n v_j\right).$$
Proof of the Lemma: We use induction on $m+n$. When $m=0$ or $n=0$, the conclusion is trivial. Assume the lemma holds for $m+n < k$. Consider the case $m+n = k$ with $m, n > 0$. Let
$$S = \max_{\text{monotone path } \mathcal{P}} W(\mathcal{P}).$$
By the induction hypothesis, for the sequences $u_0 \ge u_1 \ge \dots \ge u_{m-1}$ and $v_0 \ge v_1 \ge \dots \ge v_n$, there exists a monotone path $\mathcal{P}_0$ from $(0, 0)$ to $(m-1, n)$ such that
$$W(\mathcal{P}_0) \ge \frac{(m-1)+n+1}{m(n+1)} \left(\sum_{i=0}^{m-1} u_i\right) \left(\sum_{j=0}^n v_j\right).$$
Let $\mathcal{P}$ be the monotone path obtained by adding $(m, n)$ to $\mathcal{P}_0$, then
$$S \ge W(\mathcal{P}) = W(\mathcal{P}_0) + u_m v_n \ge \frac{(m-1)+n+1}{m(n+1)} \left(\sum_{i=0}^{m-1} u_i\right) \left(\sum_{j=0}^n v_j\right) + u_m v_n. \quad (10)$$
Similarly, for the sequences $u_0 \ge u_1 \ge \dots \ge u_m$ and $v_0 \ge v_1 \ge \dots \ge v_{n-1}$, by the induction hypothesis, we have
$$S \ge \frac{m+(n-1)+1}{(m+1)n} \left(\sum_{i=0}^m u_i\right) \left(\sum_{j=0}^{n-1} v_j\right) + u_m v_n. \quad (11)$$
Let $U = u_0 + \dots + u_m$ and $V = v_0 + \dots + v_n$. Multiplying (10) by $\frac{m}{m+n}$ and adding it to (11) multiplied by $\frac{n}{m+n}$, we get
$$\begin{align*} S &\ge \frac{1}{n+1}(U - u_m)V + \frac{1}{m+1}U(V - v_n) + u_m v_n \\ &= \frac{m+n+1}{(m+1)(n+1)}UV + \left(\frac{U}{m+1} - u_m\right)\left(\frac{V}{n+1} - v_n\right) \\ &\ge \frac{m+n+1}{(m+1)(n+1)}UV, \end{align*}$$
thereby completing the proof of the lemma.

Returning to the proof of the stated inequality. Sort $\{a_i\}$ as $u_0 \ge u_1 \ge \dots \ge u_m$, and sort $\{b_j\}$ as $v_0 \ge v_1 \ge \dots \ge v_n$. There exists a permutation $\pi$ of $\{0, 1, \dots, m\}$ such that for each index $i$, $u_i = a_{\pi(i)}$; similarly, there exists a permutation $\sigma$ of $\{0, 1, \dots, n\}$ such that for each index $j$, $v_j = b_{\sigma(j)}$.
By the lemma, there exists a monotone path $\mathcal{P} = \{(i_0, j_0), (i_1, j_1), \dots, (i_{m+n}, j_{m+n})\}$ from (0,0) to (m,n) such that
$$W(\mathcal{P}) \ge \frac{m+n+1}{(m+1)(n+1)} UV.$$
From the definition of a monotone path, for each index $k \in \{0, 1, \dots, m+n\}$ we have
$$\#\{i_0, i_1, \dots, i_k\} = i_k + 1, \quad \#\{j_0, j_1, \dots, j_k\} = j_k + 1,$$
hence
$$\#\{\pi(i_0), \dots, \pi(i_k)\} + \#\{\sigma(j_0), \dots, \sigma(j_k)\} = i_k + j_k + 2 = k + 2.$$
For finite non-empty sets of real numbers $X$ and $Y$, we have $|X + Y| \ge |X| + |Y| - 1$. Let $\Sigma_k = \{\pi(i_0), \dots, \pi(i_k)\} + \{\sigma(j_0), \dots, \sigma(j_k)\}$, then $\Sigma_k \subseteq \{0, 1, \dots, m+n\}$ and $|\Sigma_k| \ge k + 1$. Thus, we can sequentially choose
$$\tau(0) \in \Sigma_0, \quad \tau(k) \in \Sigma_k \setminus \{\tau(0), \tau(1), \dots, \tau(k-1)\}, \quad \forall 1 \le k \le m+n.$$
Since $\tau(0), \dots, \tau(m+n)$ are distinct and between 0 and $m+n$, they form a permutation of $\{0, 1, \dots, m+n\}$. For each $k$, let $\tau(k) = \pi(i_p) + \sigma(j_q)$, where $p, q \le k$. From the definition of $c_*$, we have
$$c_{\tau(k)} \ge a_{\pi(i_p)} b_{\sigma(j_q)} = u_{i_p} v_{j_q} \ge u_{i_k} v_{j_k},$$
thus,
$$\sum_{k=0}^{m+n} c_k = \sum_{k=0}^{m+n} c_{\tau(k)} \ge \sum_{k=0}^{m+n} u_{i_k} v_{j_k} = W(\mathcal{P}) \ge \frac{m+n+1}{(m+1)(n+1)} UV,$$
which proves the desired inequality. $\square$

Proof 2 (Based on the solution by Junfeng Tian). Consider the set of points $\mathcal{P} = \{(i_0, j_0), (i_1, j_1), \dots, (i_{m+n}, j_{m+n})\}$ as a "monotone path" from (0,0) to (m,n) if $(i_0, j_0) = (0,0)$, $(i_{m+n}, j_{m+n}) = (m,n)$, and for every index $0 \le k < m+n$, we have
$$(i_{k+1}, j_{k+1}) \in \{(i_k + 1, j_k), (i_k, j_k + 1)\}.$$
Noting that $i_k + j_k = k$, we get
$$\sum_{k=0}^{m+n} a_{i_k} b_{j_k} \le \sum_{k=0}^{m+n} c_{i_k + j_k} = \sum_{k=0}^{m+n} c_k.$$
We call the left-hand side of the above expression the weight of the monotone path $\mathcal{P}$, denoted as $W(\mathcal{P})$. To prove the conclusion, we only need to prove the following proposition ($*$): There exists a monotone path $\mathcal{P}$ such that
$$W(\mathcal{P}) \ge \frac{m+n+1}{(m+1)(n+1)} \sum_{i=0}^m a_i \sum_{j=0}^n b_j.$$
First, establish the following lemma: Let $0 \le x, y \le 1$, then
$$xy + \max \left\{ \frac{m+n}{m(n+1)}(1-x), \frac{m+n}{(m+1)n}(1-y) \right\} \ge \frac{m+n+1}{(m+1)(n+1)}.$$
Proof of the lemma: Let the left-hand side of the above expression be $L$. By symmetry, assume $\frac{m+n}{m(n+1)}(1-x) \ge \frac{m+n}{(m+1)n}(1-y)$, then
$$y \ge 1 - \frac{(m+1)n}{m(n+1)}(1-x).$$
Combining with the fact that $x$ is non-negative, we get
$$\begin{aligned} L &\ge x \left(1 - \frac{(m+1)n}{m(n+1)}(1-x)\right) + \frac{m+n}{m(n+1)}(1-x) \\ &= \frac{m+n+1}{(m+1)(n+1)} + \frac{n}{m(m+1)(n+1)}((m+1)x - 1)^2 \\ &\ge \frac{m+n+1}{(m+1)(n+1)}, \end{aligned}$$
thereby completing the proof of the lemma.

Returning to the proof of proposition $(*)$. We use induction on $m+n$. When $m=0$ or $n=0$, the proposition is clearly true. Assume the proposition holds for $m+n < \ell$, consider the case $m+n = \ell$ with $m, n > 0$. By homogeneity, assume $\sum_{i=0}^m a_i = \sum_{j=0}^n b_j = 1$, then $0 \le a_0, b_0 \le 1$. Let
$$S = \max_{\text{monotone path } \mathcal{P}} W(\mathcal{P}).$$
By the induction hypothesis, there exists a monotone path $P_0$ from $(1,0)$ to $(m,n)$ such that
$$W(P_0) \ge \frac{m+n}{m(n+1)} \sum_{i=1}^m a_i \sum_{j=0}^n b_j = \frac{m+n}{m(n+1)}(1-a_0).$$
Let $\mathcal{P}$ be the monotone path obtained by going from $(0,0)$ to $(1,0)$ and then following $P_0$, then
$$S \ge W(\mathcal{P}) = a_0 b_0 + \frac{m+n}{m(n+1)}(1-a_0).$$
Similarly, consider going from $(0,0)$ to $(0,1)$ and then using the induction hypothesis, we get
$$S \ge a_0 b_0 + \frac{m+n}{(m+1)n}(1-b_0).$$
Combining these two expressions and using the lemma, we get
$$S \ge a_0 b_0 + \max \left\{ \frac{m+n}{m(n+1)}(1-a_0), \frac{m+n}{(m+1)n}(1-b_0) \right\} \ge \frac{m+n+1}{(m+1)(n+1)},$$
which completes the proof. $\Box$