Zeroes are written in all cells of a $5 \times 5$ board. We can take an arbitrary cell and increase by 1 the number in this cell and all cells having a common side with it. Is it possible to obtain the number 2012 in all cells simultaneously?
Problem
Source: 2012 Baltic Way, Problem 9
Tags: combinatorics unsolved, combinatorics
25.11.2012 23:59
This is an original solution to the problem I found on the Internet: Divide all cells into six disjoint sets as follows: the set $A$ consists of all corner cells, the set $B$ consists of all cells, having a common side with the corner cells, the set $C$ consists of all diagonal neighbors of the corner cells, the set $D$ consists of all middle cells of the sides of the board, the set $E$ consists of all cells having a common side with the center cell, and the set $F$ has only the center cell in it. Suppose we choose $a$ times a cell from the set $A$, $b$ times from the set $B$ etc. Suppose that after a number of steps we get the number $s$ written in each cell. Since only the cells from the sets $A$ and $B$ contribute to the numbers written in the cells of the set $A$ and each choice from these sets contributes exactly $1$ to the sum of the numbers written in the cells of the set $A$, we have $a + b = 4s$. Similarly, considering the sum of the numbers written in the cells of the set $B$, we see that choosing a cell from the set $A$ contributes $2$ to the sum, choosing a cell from the set $B$ contributes $1$, a cell from $C$ contributes $2$ and a cell from $D$ contributes $2$, hence $2a + b + 2c + 2d = 8s$. Continuing, we get $b + c + 2e = 4s$, $b + d + e = 4s$, $2c + d + e + 4f = 4s$, and $e + f = s$. Eliminating $a$, $b$, $d$, $e$, and $f$ from these equations we get $11c = 4s$. This is only possible if $s$ is divisible by $11$. Since $2012$ is not divisible by $11$, it is not possible to get $2012$ written in each cell.