IMO 2004 SL C4

Origin: POL | Category: Combinatorics

Problem

Consider a matrix of size n\timesn whose entries are real numbers of absolute value not exceeding 1, and the sum of all entries is 0. Let n be an even positive integer. Determine the least number C such that every such matrix necessarily has a row or a column with the sum of its entries not exceeding C in absolute value.

Solution

Consider the matrix A = (aij)n i,j=1 such that aij is equal to 1 if i, j \leqn/2, −1 if i, j > n/2, and 0 otherwise. This matrix satisfies the conditions from the problem and all row sums and column sums are equal to \pmn/2. Hence C \geqn/2. Let us show that C = n/2. Assume to the contrary that there is a matrix B = (bij)n i,j=1 all of whose row sums and column sums are either greater than n/2 or smaller than −n/2. We may assume w.l.o.g. that at least n/2 row sums are positive and, permuting rows if necessary, that the first n/2 rows have positive sums. The sum of entries in the n/2 \times n submatrix B′ consisting of first n/2 rows is greater than n2/4, and since each column of B′ has sum at most n/2, it follows that more than n/2 column sums of B′, and therefore also of B, are positive. Again, suppose w.l.o.g. that the first n/2 column sums are positive. Thus the sums R+ and C+ of entries in the first n/2 rows and in the first n/2 columns respectively are greater than n2/4. Now the sum of all entries of B can be written as  aij = R+ + C+ +  i>n/2 j>n/2 aij −  i\leqn/2 j\leqn/2 aij > n2 2 −n2 4 −n2 4 = 0, a contradiction. Hence C = n/2, as claimed.