IMO 2003 SL C4

Origin: IRN | Category: Combinatorics

Problem

Let x1, . . . , xn and y1, . . . , yn be real numbers. Let A = (aij)1\leqi,j\leqn be the matrix with entries aij = . 1, if xi + yj \geq0; 0, if xi + yj < 0. Suppose that B is an n \times n matrix whose entries are 0, 1 such that the sum of the elements in each row and each column of B is equal to the corresponding sum for the matrix A. Prove that A = B.

Solution

Denote by bij the entries of the matrix B. Suppose the contrary, i.e., that there is a pair (i0, j0) such that ai0,j0 ̸= bi0,j0. We may assume without loss of generality that ai0,j0 = 0 and bi0,j0 = 1. Since the sums of elements in the i0th rows of the matrices A and B are equal, there is some j1 for which ai0,j1 = 1 and bi0,j1 = 0. Similarly, from the fact that the sums in the j1th columns of the matrices A and B are equal, we conclude that there exists i1 such that ai1,j1 = 0 and bi1,j1 = 1. Continuing this procedure, we construct two sequences ik, jk such that aik,jk = 0, bik,jk = 1, aik,jk+1 = 1, bik,jk+1 = 0. Since the set of the pairs (ik, jk) is finite, there are two different numbers t, s such that (it, jt) = (is, js). From the given condition we have that xik + yik < 0 and xik+1 + yik+1 \geq0. But jt = js, and hence 0 \leqt−1 k=s(xik + yjk+1) = t−1 k=s(xik + yjk) < 0, a contradiction.