Maths Olympiad Prep

Library / /392 of 520

Combinatorics Difficulty 7.2 National olympiad, round 2 Prove it

9.83 In an m×mm \times m grid, each small square is filled with a non-negative integer. If a small square is filled with 0, then the sum of the numbers in all the small squares in the row and column containing this small square is not less than mm. Prove that the sum of all the numbers in the grid is not less than m22\frac{m^{2}}{2}.

---

The translation preserves the original formatting and structure of the text.

Solution

[Proof] Consider the sum of the numbers filled in each row and each column, and let the smallest of these 2m2m numbers be denoted as pp. Without loss of generality, assume pp is the sum of the numbers in the first row. If pm2p \geqslant \frac{m}{2}, then the conclusion to be proven is obviously true. Suppose p<m2p < \frac{m}{2}. By estimating the sum of the numbers filled in each column, we can see that the total sum SS of all numbers filled in the table satisfies
S(mp)k+(mk)p=m(k+p)2pk=m(k+p)12(p+k)2+12(pk)2=m22+12(pk)212(p+km)2=m22+12(2pm)(m2k)>m22\begin{aligned} S & \geqslant (m-p) k + (m-k) p = m(k + p) - 2 p k \\ & = m(k + p) - \frac{1}{2}(p + k)^{2} + \frac{1}{2}(p - k)^{2} \\ = & \frac{m^{2}}{2} + \frac{1}{2}(p - k)^{2} - \frac{1}{2}(p + k - m)^{2} = \frac{m^{2}}{2} + \frac{1}{2}(2 p - m)(m \\ & - 2 k) \\ & > \frac{m^{2}}{2} \end{aligned}

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.