Prove that all the numbers in the table are even.

Question

In each cell of a 20 x 20 table an integer is written , such that for every 7 rows and 7 columns that we consider the sum of these 49 cells (the cells where the rows and columns intersect) is an even number. Prove that all the numbers in the table are even.

Answer 1

HINT to an alternate solution, partly inspired by @JaapScherphuis and partly inpsired by linear algebra (modulo $2$, i.e. in $\mathbb{F}_2$).

Let $A$ denote the original $20\times 20$ table, $R$ denote a subset of rows, $C$ denote a subset of columns, and

$$S(R,C) = \sum_{r \in R \\ c \in C} A_{r,c}$$

be the sum of numbers in the intersection of those rows and those columns.

(1) You are given that: $S(R,C)$ is even whenever $|R|=|C|=7$, i.e. there are $7$ rows and $7$ columns.

(2) Prove, by repeated applications of (1), that $S(R,C)$ is even whenever $|R|=7, |C|=2$.

(3) Prove, from (1) & (2) together, that $S(R,C)$ is even whenever $|R|=7, |C|=1$, i.e. for the single column case.

Now you go through the analogous process to shrink the number of rows:

(4) Prove, from (3), that $S(R,C)$ is even whenever $|R|=2, |C|=1$.

(5) Prove, from (3) & (4) together, that $S(R,C)$ is even whenever $|R|=|C|=1$, i.e. every cell is even. QED

BTW: this method also clearly shows that the result works only because $7$ itself is odd. If the initial condition were $S(R,C)$ is even whenever $|R|=|C|=6$, then (step 3) breaks down, and indeed there are many counter-examples, e.g. the all-odd grid, checkerboard of odds and evens, etc.

Answer 2

Here is one way to do it.

First prove that the sum of any 4 cells in a rectangle (the intersection of two rows and two column) is even. This is done by carefully selecting various sets of 7 rows by 7 columns, and subtracting them from each other.

Next you have to see that you are free to rearrange the rows or rearrange the columns of the large table, without changing the fact that it satisfies the conditions of the problem.

Assuming there is an odd entry somewhere in the table, you can rearrange the rows/columns so that that number is in the top-left corner. Then rearrange the remaining columns so that the first row has all the odd numbers first, followed by the even numbers (if any). Also rearrange the remaining rows so that the first column has its odd numbers at the top, followed by any even numbers underneath.

If you have this top row and left column starting with odd numbers, work out where the odd and even numbers must be in the rest of the table. Finally show that there is some 7x7 section that fails the conditions. This means that the assumption that there was an odd entry in the table must have been wrong, so there can only be even numbers in the table.