IMO 1971 SL 13

Origin: SWE

Problem

Consider the n \times n array of nonnegative integers ⎛ ⎜ ⎜ ⎜ ⎝ a11 a12 . . . a1n a21 a22 \cdot \cdot \cdot a2n ... ... ... an1 an2 . . . ann ⎞ ⎟ ⎟ ⎟ ⎠, with the following property: If an element aij is zero, then the sum of the elements of the ith row and the jth column is greater than or equal to n. Prove that the sum of all the elements is greater than or equal to 1 2n2.

Solution

Let p be the least of all the sums of elements in one row or column. If p \geqn/2, then the sum of all elements of the array is s \geqnp \geqn2/2.

Now suppose that p < n/2. Without loss of generality, one can assume that the sum of elements in the first row is p, and that exactly the first q elements of it are different from zero. Then the sum of elements in the last n−q columns is greater than or equal to (n−p)(n−q). Furthermore, the sum of elements in the first q columns is greater than or equal to pq. This implies that the sum of all elements in the array is s \geq(n −p)(n −q) + pq = 1 2n2 + 1 2(n −2p)(n −2q) \geq1 2n2, since n \geq2p \geq2q.