Inequality with ordering

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Inequality with ordering

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: 2021 China TST, Test 1, Day 1 P1

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

JustPostChinaTST

38 posts

JustPostChinaTST

#1 h Mar 17, 2021, 12:54 PM • 3 Y

Y by mlgjeffdoge21, Rg230403, Mango247

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}.$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

590 posts

XbenX

#2 h Mar 18, 2021, 8:39 AM • 1 Y

Y by guptaamitu1

Solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

19 posts

#3 h Mar 20, 2021, 12:29 AM

Y by

Solution

This post has been edited 1 time. Last edited by xiejiesuo, Mar 20, 2021, 12:29 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1301 posts

#4 h Mar 20, 2021, 1:13 AM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

235 posts

DNCT1

#5 h Mar 21, 2021, 5:27 PM

Y by

xiejiesuo wrote:

Solution

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1301 posts

#6 h Mar 21, 2021, 5:55 PM • 2 Y

Y by DNCT1, Mathematicsislovely

$\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$ .

This post has been edited 3 times. Last edited by CANBANKAN, Mar 21, 2021, 8:32 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

21 posts

#7 h Dec 14, 2021, 7:32 PM • 1 Y

Y by bo18

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.

This post has been edited 1 time. Last edited by CHOUKRI, Dec 14, 2021, 7:34 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

934 posts

#8 h Mar 22, 2025, 9:17 AM

Y by

The main idea is to not be scared, and laugh in the face of symbols.
We have:

Claim: $X_{i,j}X_{m+1-i,n+1-j} \ge Y_{i,j}Y_{m+1-i,n+1-j}$ for all $1 \le i \le m, 1 \le n \le j$ .
Proof sketch: Expand, and then bound each factor with the largest/smallest term in the product as required.

From here, multiply this claim over all $i,j$ : If $mn$ is even, taking the square root gives us the inequality outright. Else, don't multiply the inequality for $(i,j) = (\frac{m+1}2, \frac{n+1}2)$ , and instead use the fact that $X_{\frac{m+1}2,\frac{n+1}2} \ge Y_{\frac{m+1}2,\frac{n+1}2}$ , to get the inequality. $\square$

Remark: There's a nice way to visualise this using an $m \times n$ grid.

This post has been edited 1 time. Last edited by AshAuktober, Mar 22, 2025, 9:26 AM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a