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.
Prove that all the numbers in the table are even.
discrete mathematicsinvariancepuzzle
Related Solutions
We have the following figure 
We know that for the numbers $5$ and $6$, the sum of the numbers in the neighboring cells is equal to 13.
When $c_1=5$ or $6$ then it would have to hold that $1+2+c_3=13 \Rightarrow c_3=10$. This cannot be true since the greatest number is $9$.
When $c_5=5$ or $6$ then it would have to hold that $4+3+c_3=13 \Rightarrow c_3=6$.
So, it must be $c_5=5$. That means that it must hold $4+6+3=13$. This is true.
The sum of the neighboring cells of $c_3=6$ is $c_1+c_2+c_3+c_4=5+7+8+9>13$.
($7,8,9$ are the left numbers that have to be in these cells.)
This case is not possible.
When $c_4=5$ or $6$ then it would have to hold that $2+3+c_3=13 \Rightarrow c_3=8$.
Without loss of generality, we suppose that $c_4=5$.
Now we have to look in which cell is the number $6$.
We check the cell $c_5$. When $c_5=6$, then it must hold that $4+8+3=13$. Which is not true.
So, the only possibility is that $c_2=6$. Then it must hold that $1+8+4=13$, which is true.
Therefore, at the cells $c_2,c_4$ there are the numbers $5,6$ and at the shaded cell $c_3$ there is the number $8$.
Hint: Stick $99\times 99$ needles on this grid, each at a place where four cells meet in a corner. For each pair of needles at distance one apart, connect them with a piece of string if the the two squares touching the edge between them have different colors.
Each needle with have either $2$ or $4$ pieces of string tied to it (why?). If a needle has four strings, then the four squares surrounding it are colored like a checkerboard. So, assume to the contrary that every needle only has two strings. What would the resulting picture look like? Why is that impossible?
Further hint:
If every needle only had two strings, then the needles would be partitioned into "loops," where each needle is connected to a the next and previous in a circular fashion. What are the possible sizes of a loop?
For example, you can have a loop of size four where the four needles are the vertices of a cell. Can you have a loop of size $5$?
Best Answer
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.