A positive integer is written in each square of an m x n board. The allowed move is to add an integer k to each of two adjacent numbers (whose squares have a common side). Find a necessary and sufficient condition for it to be possible to get all numbers zero by a finite sequence of moves.
Solution
Answer: color the squares alternately black and white as on a chessboard. We can get all zeros iff the sum of the numbers on the black squares equals the sum of the numbers on the white squares.
The condition is clearly necessary, because if ∑black denotes the sum of the numbers on the black squares and ∑white the sum of the numbers on the white squares, then ∑black - ∑white is invariant.
So suppose the condition holds. By adding enough to every adjacent pair in the second row, we can ensure that each number in the second row is at least as large as the integer above it in the first row. Then for each integer in the first row subtract it from itself and the integer below. That zeros the first row. Similarly, we can zero each row except the bottom row.
We now work along the bottom row in a similar way. We start by adding enough to the integers in columns 2 and 3, so that the number in column 2 is at least as large as the number in column 1. Then subtract the number in column 1 from that in column 1 and column 2, thus zeroing the number in column 1. In this way we zero all except the last two numbers in the row. But by the invariant they must be equal, so we can zero them both simultaneously.
© John Scholes
jscholes@kalva.demon.co.uk
28 Dec 2002
Last corrected/updated 28 Dec 02