The cells of a rectangular board are colored in the chess manner. Every cell is filled with an integer. Assume that the sum of numbers in any row and in any column is even. Prove that the sum of numbers in the black cells is even.
Problem
Source: Ukraine 1997 grade 9
Tags: combinatorics proposed, combinatorics
21.07.2009 19:36
We claim that any such board can be generated starting from a board of all evens and iteratively performing the following operation: choose two rows and two columns and switch the parities of the numbers in the four squares where these rows and columns intersect. Proof: Start with an all even board and suppose $ B$ is the one we want to generate. Suppose the board is width $ n$ and the columns are $ C_0, C_1, \ldots C_{n-1}$. For each $ i = 1, 2, \ldots n-1$, perform the operation on $ C_0, C_i$ and the appropriate rows until $ C_i$ has same parity configuration of $ B$. Because the sum of each column is even and we act on each $ C_i$ independently, we know we can do this. All we have to check is that $ C_0$ is correct. But since all of the row sums are even, $ C_0$ is uniquely determined from the other columns $ C_1, C_2, \ldots C_{n-1}$, and our operation keeps this condition invariant. So we must have generated the correct $ C_0$ as well, and so we have generated all of $ B$. Each time perform the operation we do not change the parity of the sum of the black cells (or white cells). Since initially the sum of all of the black cells was even, the same holds true in the final board, which is what we wanted.