Maths Olympiad Prep

Library / /65 of 82

Combinatorics Difficulty 6.2 National olympiad Prove it Croatia

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

Solution

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 KK moves the sums of numbers in each row and each column is equal and let us denote it by SS. The sum of all numbers is then equal to NSN \cdot S. Since this must be even and NN is odd, we conclude that SS 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 AiA_i denote the number of moves that change the numbers in two squares in ii-th and (i+1)(i+1)-st columns.

Number A1A_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 A1+A2A_1 + A_2, hence A2A_2 is even. Inductively, we conclude that every AiA_i is even.

Hence the total number of moves that will change the parity of two columns is A1+A2++An1A_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.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.