Maths Olympiad Prep

Library / /25 of 48

Algebra Difficulty 8.5 Shortlist Prove it China

Let m,nm, n be positive integers, aija_{ij} (1im,1jn1 \le i \le m, 1 \le j \le n) be nonnegative real numbers such that for any i,ji, j, the inequalities
ai,1ai,2ai,n,a1,ja2,jam,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++ai1,j+ai,j+ai,j1++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=1mj=1nXi,ji=1mj=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+j1)ai,j,Yi,j(m+nij+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=1mj=1nXi,ji=1mj=1n(i+j1)ai,j=i=1mj=1n(m+nij+1)ai,ji=1mj=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+1i,n+1j)(i, j) \leftrightarrow (m + 1 - i, n + 1 - j), and i+j1i + j - 1 corresponds to m+nij+1m + n - i - j + 1.

Solution 2

We shall use the following inequality:
For 0c1ct0 \le c_1 \le \cdots \le c_t, 0d1dt0 \le d_1 \le \cdots \le d_t,
(c1+d1)(c2+d2)(ct+dt)(c1+dt)(c2+dt1)(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+1i+dt+1i)(ci+dt+1i)(ct+1i+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+1i+dt+1i))i=1t((ci+dt+1i)(ct+1i+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,jai,j,Yi,j=Di,j+Ri,jai,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=1mj=1nXi,j=i=1mj=1n(Li,j+(Ui,jai,j))i=1mj=1n(Li,n+1j+(Ui,jai,j))(since {Li,j}j=1n increases while {Ui,jai,j}j=1n decreases)i=1mj=1n(Ri,j+(Ui,jai,j))(since Li,n+1jRi,j)=j=1ni=1m((Ri,jai,j)+Ui,j)j=1ni=1m((Ri,jai,j)+Um+1i,j)(since {Ri,jai,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=1ni=1m((Ri,jai,j)+Di,j)(since Um+1i,jDi,j)=i=1mj=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,000 problems in a working order, from AMC 10 level to the IMO shortlist.

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