Mathematica competitions in Croatia

Question

Let N 3 be an odd positive integer. At the beginning in each square of an N N board there is number 0. In one move one can choose two squares with a common side and increase or decrease by 1 the numbers in those two squares. If after K moves, the sums of numbers in every row and every column are all equal, show that K is even. (USSR)

Accepted Answer

In each move the sum of all numbers increases or decreases by two, so the sum of all numbers remains even. Let us assume that after

K

moves the sums of numbers in each row and each column is equal and let us denote it by

S

. The sum of all numbers is then equal to

N \cdot S

. Since this must be even and

N

is odd, we conclude that

S

must be even.

Note that in each move we change the parity of the sum of two adjacent rows or two adjacent columns. First we consider only the moves that change the parity of two adjacent columns. Let

A_{i}

denote the number of moves that change the numbers in two squares in

i

-th and

(i + 1)

-st columns.

Number

A_{1}

must be even because these are the only moves that will change the parity of the sum in the first column. The number of moves that will change the parity of the sum in the second column also has to be even and it is

A_{1} + A_{2}

, hence

A_{2}

is even. Inductively, we conclude that every

A_{i}

is even.

Hence the total number of moves that will change the parity of two columns is

A_{1} + A_{2} + \dots + A_{n - 1}

, which is an even number. Analogously, the total number of moves that will change the parity of two rows is an even number. We conclude that the total number of moves is also even.