IMO 1998 SL 22

Origin: UKR

Problem

A rectangular array of numbers is given. In each row and each column, the sum of all numbers is an integer. Prove that each nonintegral number x in the array can be changed into either \lceilx\rceilor \lfloorx\rfloorso that the row sums and column sums remain unchanged. (Note that \lceilx\rceilis the least integer greater than or equal to x, while \lfloorx\rflooris the greatest integer less than or equal to x.)

Solution

We can obviously change each x into \lfloorx\rflooror \lceilx\rceilso that the column sums remain unchanged. However, this does not necessarily match the row sums as well, so let us consider the sum S of the absolute values of the changes in the row sums. It is easily seen that S is even, and we want it to be 0. A row may have a higher or lower sum than desired. Let us mark a cell by −if its entry x was changed to \lfloorx\rfloor, and by + if it was changed to \lceilx\rceil instead. We call a row R2 accessible from a row R1 if there is a column C such that C \capR1 is marked + and C \capR2 is marked −. Note that a column containing a + must contain a −as well, because column sums are unchanged. Hence from each row with a higher sum we can access another row. Assume that the row sum in R1 is higher. If R1, R2, . . . , Rk is a sequence of rows such that Ri+1 is accessible from Ri via some column Ci and such that the row sum in Rk is lower, then by changing the signs in Ci \capRi and Ci \capRi+1 (i = 1, 2, . . . , k −1) we decrease S by 2, leaving column sums unchanged. We claim that such a sequence of rows always exists. Let R be the union of all rows that are accessible from R1, directly or indirectly; let R be the union of the remaining rows. We show that for any column C, the sum in R \capC is not higher. If R \capC contains no +’s, then this is clear. If R \capC contains a +, since the rows of R are not accessible, the set R \capC contains no −’s. It follows that the sum in R \capC is not lower, and since column sums are unchanged, we again come to the same conclusion. Thus the total sum in R is not higher. Therefore, there is a row in R with too low a sum, justifying our claim.