IMO 1989 SL 19

Origin: MON

Problem

A positive integer is written in each square of an m\timesn board. The allowed move is to add an integer k to each of two adjacent numbers in such a way that no negative numbers are obtained. (Two squares are adjacent if they have a common side.) Find a necessary and sufficient condition for it to be possible for all the numbers to be zero by a finite sequence of moves.

Solution

Let us color the board in a chessboard fashion. Denote by Sb and Sw respectively the sum of numbers in the black and in the white squares. It is clear that every allowed move leaves the difference Sb −Sw unchanged. Therefore a necessary condition for annulling all the numbers is Sb = Sw. We now show it is sufficient. Assuming Sb = Sw let us observe a triple of (different) cells a, b, c with respective values xa, xb, xc where a and c are both adjacent to b. We first prove that we can reduce xa to be 0 if xa > 0. If xa \leqxb, we subtract xa from both a and b. If xa > xb, we add xa −xb to b and c and proceed as in the previous case. Applying the reduction in sequence, along the entire board, we reduce all cells except two neighboring cells to be 0. Since Sb = Sw is invariant, the two cells must have equal values and we can thus reduce them both to 0.