Maths Olympiad Prep

Library / China National Team Selection Test /24 of 46

China National Team Selection Test

Algebra Difficulty 8.5 Shortlist Prove it China

Let m,nm, n be positive integers, aija_{ij} (1≤i≤m,1≤j≤n1 \le i \le m, 1 \le j \le n) be nonnegative real numbers such that for any i,ji, j, the inequalities
ai,1≥ai,2≥⋯≥ai,n,a1,j≥a2,j≥⋯≥am,j a_{i,1} \ge a_{i,2} \ge \dots \ge a_{i,n}, \quad a_{1,j} \ge a_{2,j} \ge \dots \ge a_{m,j}
hold. For i=1,2,…,mi = 1, 2, \dots, m and j=1,2,…,nj = 1, 2, \dots, n, define
Xi,j=a1,j+⋯+ai−1,j+ai,j+ai,j−1+⋯+ai,1, X_{i,j} = a_{1,j} + \dots + a_{i-1,j} + a_{i,j} + a_{i,j-1} + \dots + a_{i,1},
Yi,j=ai,j+ai+1,j+⋯+am,j+ai,j+1+⋯+ai,n. Y_{i,j} = a_{i,j} + a_{i+1,j} + \dots + a_{m,j} + a_{i,j+1} + \dots + a_{i,n}.
Prove that
∏i=1m∏j=1nXi,j≥∏i=1m∏j=1nYi,j. \prod_{i=1}^{m} \prod_{j=1}^{n} X_{i,j} \ge \prod_{i=1}^{m} \prod_{j=1}^{n} Y_{i,j}.

Solutions — 2

Solution 1

The problem conditions imply that
Xi,j≥(i+j−1)⋅ai,j,Yi,j≤(m+n−i−j+1)⋅ai,j. X_{i,j} \ge (i + j - 1) \cdot a_{i,j}, \quad Y_{i,j} \le (m + n - i - j + 1) \cdot a_{i,j}.
Hence, we have
∏i=1m∏j=1nXi,j≥∏i=1m∏j=1n(i+j−1)⋅ai,j=∏i=1m∏j=1n(m+n−i−j+1)⋅ai,j≥∏i=1m∏j=1nYi,j, \begin{align*} \prod_{i=1}^{m} \prod_{j=1}^{n} X_{i,j} &\ge \prod_{i=1}^{m} \prod_{j=1}^{n} (i+j-1) \cdot a_{i,j} \\ &= \prod_{i=1}^{m} \prod_{j=1}^{n} (m+n-i-j+1) \cdot a_{i,j} \\ &\ge \prod_{i=1}^{m} \prod_{j=1}^{n} Y_{i,j}, \end{align*}
where the equality on the second line is due to the one-to-one correspondence (i,j)↔(m+1−i,n+1−j)(i, j) \leftrightarrow (m + 1 - i, n + 1 - j), and i+j−1i + j - 1 corresponds to m+n−i−j+1m + n - i - j + 1.

Solution 2

We shall use the following inequality:
For 0≤c1≤⋯≤ct0 \le c_1 \le \cdots \le c_t, 0≤d1≤⋯≤dt0 \le d_1 \le \cdots \le d_t,
(c1+d1)(c2+d2)⋯(ct+dt)≤(c1+dt)(c2+dt−1)⋯(ct+d1).1◯ (c_1+d_1)(c_2+d_2)\cdots(c_t+d_t) \le (c_1+d_t)(c_2+d_{t-1})\cdots(c_t+d_1). \quad \textcircled{1}
This is because, for each ii,
(ci+di)(ct+1−i+dt+1−i)≤(ci+dt+1−i)(ct+1−i+di). (c_i+d_i)(c_{t+1-i}+d_{t+1-i}) \le (c_i+d_{t+1-i})(c_{t+1-i}+d_i).
Multiplying the above inequalities for i=1,…,ti = 1, \dots, t gives
∏i=1t((ci+di)(ct+1−i+dt+1−i))≤∏i=1t((ci+dt+1−i)(ct+1−i+di)), \prod_{i=1}^{t} ((c_i+d_i)(c_{t+1-i}+d_{t+1-i})) \le \prod_{i=1}^{t} ((c_i+d_{t+1-i})(c_{t+1-i}+d_i)),
and taking the square root on both sides of the above inequality gives (1).
For the original problem, let Li,j=∑q=1jai,qL_{i,j} = \sum_{q=1}^{j} a_{i,q}, Ri,j=∑q=jnai,qR_{i,j} = \sum_{q=j}^{n} a_{i,q},
Ui,j=∑p=1iap,j,Di,j=∑p=imap,j. U_{i,j} = \sum_{p=1}^{i} a_{p,j}, \quad D_{i,j} = \sum_{p=i}^{m} a_{p,j}.
Then
Xi,j=Li,j+Ui,j−ai,j,Yi,j=Di,j+Ri,j−ai,j. X_{i,j} = L_{i,j} + U_{i,j} - a_{i,j}, \quad Y_{i,j} = D_{i,j} + R_{i,j} - a_{i,j}.
Apply (1) to derive
∏i=1m∏j=1nXi,j=∏i=1m∏j=1n(Li,j+(Ui,j−ai,j))≥∏i=1m∏j=1n(Li,n+1−j+(Ui,j−ai,j))(since {Li,j}j=1n increases while {Ui,j−ai,j}j=1n decreases)≥∏i=1m∏j=1n(Ri,j+(Ui,j−ai,j))(since Li,n+1−j≥Ri,j)=∏j=1n∏i=1m((Ri,j−ai,j)+Ui,j)≥∏j=1n∏i=1m((Ri,j−ai,j)+Um+1−i,j)(since {Ri,j−ai,j}i=1m decreases while {Ui,j}i=1m increases) \begin{align*} \prod_{i=1}^{m} \prod_{j=1}^{n} X_{i,j} &= \prod_{i=1}^{m} \prod_{j=1}^{n} (L_{i,j} + (U_{i,j} - a_{i,j})) \\ &\ge \prod_{i=1}^{m} \prod_{j=1}^{n} (L_{i,n+1-j} + (U_{i,j} - a_{i,j})) \\ &\quad \text{(since } \{L_{i,j}\}_{j=1}^{n} \text{ increases while } \{U_{i,j} - a_{i,j}\}_{j=1}^{n} \text{ decreases)} \\ &\ge \prod_{i=1}^{m} \prod_{j=1}^{n} (R_{i,j} + (U_{i,j} - a_{i,j})) \quad \text{(since } L_{i,n+1-j} \ge R_{i,j}) \\ &= \prod_{j=1}^{n} \prod_{i=1}^{m} ((R_{i,j} - a_{i,j}) + U_{i,j}) \\ &\ge \prod_{j=1}^{n} \prod_{i=1}^{m} ((R_{i,j} - a_{i,j}) + U_{m+1-i,j}) \\ &\quad \text{(since } \{R_{i,j} - a_{i,j}\}_{i=1}^{m} \text{ decreases while } \{U_{i,j}\}_{i=1}^{m} \text{ increases)} \end{align*}
≥∏j=1n∏i=1m((Ri,j−ai,j)+Di,j)(since Um+1−i,j≥Di,j)=∏i=1m∏j=1nYi,j. \begin{align*} &\ge \prod_{j=1}^{n} \prod_{i=1}^{m} ((R_{i,j} - a_{i,j}) + D_{i,j}) \quad (\text{since } U_{m+1-i,j} \ge D_{i,j}) \\ &= \prod_{i=1}^{m} \prod_{j=1}^{n} Y_{i,j}. \end{align*}

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.