Let A = (aij), where i, j = 1, 2, ... , n, be a square matrix with all aij non-negative integers. For each i, j such that aij = 0, the sum of the elements in the ith row and the jth column is at least n. Prove that the sum of all the elements in the matrix is at least n2/2.
Solution
Let x be the smallest row or column sum. If x >= n/2, then we are done, so assume x < n/2. Suppose it is a row. (If not, interchange rows and columns.) The number of non-zero elements in the row, y, must also satisfy y < n/2, since each non-zero element is at least 1. Now move across this row summing the columns. The y columns with a non-zero element have sum at least x (by the definition of x). The n - y columns with a zero have sum at least n - x. Hence the total sum is at least xy + (n - x)(n - y) = n2/2 + (n - 2x)(n - 2y)/2 > n2/2.
The result is evidently best possible, because we can fill the matrix alternately with zeros and ones (so that aij = 1 if i and j are both odd or both even, 0 otherwise). For n even, every row and column has n/2 1s, so the condition is certainly satisfied and the total sum is n2/2. For n odd, odd numbered rows have (n+1)/2 1s and even numbered one less. But the only zeros are in positions which have either the row or the column odd-numbered, so the sum in such cases is n as required. The total sum is n2/2 + 1/2. Alternatively, for n even, we could place n/2 down the main diagonal.
Solutions are also available in: Samuel L Greitzer, International Mathematical Olympiads 1959-1977, MAA 1978, and in István Reiman, International Mathematical Olympiad 1959-1999, ISBN 189-8855-48-X.
© John Scholes
jscholes@kalva.demon.co.uk
8 Oct 1998
Last updated/corrected 14 Mar 03