Given positive integers $m$ and $n$. Let $a_{i,j} ( 1 \le i \le m, 1 \le j \le n)$ be non-negative real numbers, such that $$ a_{i,1} \ge a_{i,2} \ge \cdots \ge a_{i,n} \text{ and } a_{1,j} \ge a_{2,j} \ge \cdots \ge a_{m,j} $$holds for all $1 \le i \le m$ and $1 \le j \le n$. Denote $$ X_{i,j}=a_{1,j}+\cdots+a_{i-1,j}+a_{i,j}+a_{i,j-1}+\cdots+a_{i,1},$$$$ Y_{i,j}=a_{m,j}+\cdots+a_{i+1,j}+a_{i,j}+a_{i,j+1}+\cdots+a_{i,n}.$$Prove that $$ \prod_{i=1}^{m} \prod_{j=1}^{n} X_{i,j} \ge \prod_{i=1}^{m} \prod_{j=1}^{n} Y_{i,j}.$$
Problem
Source: 2021 China TST, Test 1, Day 1 P1
Tags: inequalities
XbenX
18.03.2021 11:39
It really helps to draw matrices on this one.
Lemma. It holds that
\begin{align}
X_{i,j}X_{m+1-i,n+1-j}\geq Y_{i,j}Y_{m+1-i,n+1-j}
\end{align}for $1\leq i\leq m,\,1\leq j\leq n$.
Proof. The summands in $X_{i,j}$ are greater than the summands in $Y_{i,j}$, and the same is true for $X_{m+1-i,n+1-j}$ and $Y_{m+1-i,n+1-j}$.
Now, since $X_{i,j}$ and $Y_{m+1-i,n+1-j}$, have the same number of summands, $Y_i$ and $X_{m+1-i,n+1-j}$ have the same number of summands,
after expanding the product we have that each term of $LHS$ is greater than that of $RHS$. $\square$
Now, taking the product of inequalities $(1)$ for $1\leq i\leq m,\,1\leq j\leq n$ then taking the square root we get the desired inequality.
xiejiesuo
20.03.2021 03:29
$$ \prod_{i=1}^{m} \prod_{j=1}^{n} X_{i,j} \ge \prod_{i=1}^{m} \prod_{j=1}^{n} (i+j-1) a_{i,j} \ge \prod_{i=1}^{m} \prod_{j=1}^{n} (m+n-i-j+1) a_{i,j} \ge \prod_{i=1}^{m} \prod_{j=1}^{n} Y_{i,j}.$$
CANBANKAN
20.03.2021 04:13
Note $X_{i,j}\ge (i+j-1)a_{i,j}$, $Y_{i,j}\le (m+n-i-j+1)a_{i,j}$, so done.
DNCT1
21.03.2021 20:27
xiejiesuo wrote:
$$ \prod_{i=1}^{m} \prod_{j=1}^{n} X_{i,j} \ge \prod_{i=1}^{m} \prod_{j=1}^{n} (i+j-1) a_{i,j} \ge \prod_{i=1}^{m} \prod_{j=1}^{n} (m+n-i-j+1) a_{i,j} \ge \prod_{i=1}^{m} \prod_{j=1}^{n} Y_{i,j}.$$
How you get that $\prod_{i=1}^{m} \prod_{j=1}^{n} (i+j-1) a_{i,j} \ge \prod_{i=1}^{m} \prod_{j=1}^{n} (m+n-i-j+1) a_{i,j}$, I was stuck here when I tried to sol the problem
CANBANKAN
21.03.2021 20:55
$\prod_{i=1}^m \prod_{j=1}^n (i+j-1) = \prod_{i=1}^m \prod_{j=1}^n (m+n-i-j+1)$. This is true because we can pair $(i,j)$ with $(m+1-i,n+1-j)$. Another way to see this is that on both sides, $x$ is counted $\min\{x,2n-x\}$ times for $1\le x\le 2n-1$.
CHOUKRI
14.12.2021 22:32
First, we saw that for any couple $(i,j)$ of index, we have $$\dfrac{Y_{i,j}}{n+m+1-i-j}\leq a_{i,j}\leq \dfrac{X_{i,j}}{i+j-1},\quad\quad\quad\quad\quad (*) $$Hence, by multuplying all inequalities (formed by $LHS$ and $RHS$ of $(*)$) for $i=1,\ldots,n$ and $j=1,\ldots,m$, we get $$\dfrac{1}{\displaystyle \prod_{i,j}((n+1-i)+(m+1-j)-1)}\times \prod_{i=1}^{m} \prod_{j=1}^{n} Y_{i,j}\leq \dfrac{1}{\displaystyle\prod_{i,j}(i+j-1)}\times\prod_{i=1}^{m} \prod_{j=1}^{n} X_{i,j} $$ But, $$\displaystyle \prod_{i,j}((n+1-i)+(m+1-j)-1)=\displaystyle\prod_{i,j}(i+j-1) $$ Finally, we get the desired inequality.