The 65th 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 \cdots \ge u_m$ and $v_0\ge v_1\ge \cdots \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=\underset{\text{monotone path }\mathcal{P}}{\max }W(\mathcal{P}).$$ By the induction hypothesis, for the sequences $u_0\ge u_1\ge \cdots \ge u_{m-1}$ and $v_0\ge v_1\ge \cdots \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.(10)$$ Similarly, for the sequences $u_0\ge u_1\ge \cdots \ge u_m$ and $v_0\ge v_1\ge \cdots \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.(11)$$ Let $U=u_0+\cdots +u_m$ and $V=v_0+\cdots +v_n$. Multiplying (10) by $\frac{m}{m+n}$ and adding it to (11) multiplied by $\frac{n}{m+n}$, we get $$\begin{array}{rl}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{array}$$ 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 \cdots \ge u_m$, and sort $\{b_j\}$ as $v_0\ge v_1\ge \cdots \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,\#\{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,\tau (k)\in {\Sigma }_k\setminus \{\tau (0),\tau (1),\dots ,\tau (k-1)\},\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_{\ast }$, 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$

---

Alternative solution.

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 ($\ast$): 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{array}{rl}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{array}$$ thereby completing the proof of the lemma.

Returning to the proof of proposition $(\ast )$. 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=\underset{\text{monotone path }\mathcal{P}}{\max }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. $\square$