Mathematical Reflections 2016, Issue 3 - Problem O373

Problem:Let $n \geq 3$ be a natural number. On a $n \times n$ table we perform the following operation: choose a $(n-1) \times (n-1)$ square and add or subtract $1$ to all its entries. At the beginning all the entres in the table are $0$. Is it possible after a finite number of operations to obtain all the natural numbers from $1$ to $n^2$ in the table?

Proposed by Alessandro Ventullo, Milan, Italy

Solution:
The answer is no. Observe that after each operation on a $(n-1) \times (n-1)$ square, the sum of all the elements in the $n \times n$ table is constant modulo $(n-1)^2$. Since at the beginning the table is filled with zeros, then after any finite number of operations the sum of the elements in the table is divisible by $(n-1)^2$. On the other hand, $$S=1+2+\ldots+n^2=\dfrac{n^2(n^2+1)}{2}.$$
If $n$ is even, then $n=2k$ where $k \geq 2$, and $$S=2k^2(4k^2+1).$$ Assume that $(2k-1)^2 \ | \ S$. Then $(2k-1)^2 \ | \ 2S=4k^2(4k^2+1)$. Since $(2k-1,2k)=1$, then $((2k-1)^2,4k^2)=1$. It follows that $(2k-1)^2 \ | \ (4k^2+1)$, i.e. $(2k-1)^2 \ | \ 4k$. This leads to $(2k-1)^2 \leq 4k$, which is false for $k \geq 2$.
If $n$ is odd, then $n=2k+1$, where $k \geq 1$ and $$S=(2k+1)^2(2k^2+2k+1).$$ Assume that $4k^2 \ | \ S$. Then $4k^2 \ | \ 2S=(2k+1)^2(4k^2+4k+2)$. Since $(2k,2k+1)=1$, then $(4k^2,(2k+1)^2)=1$. It follows that $4k^2 \ | \ (4k^2+4k+2)$, i.e. $4k^2 \ | \ (4k+2)$. This leads to $4k^2 \leq 4k+2$, which is false for $k \geq 2$. Moreover, if $k=1$, then $4 \nmid 6$.
In conclusion, $(n-1)^2$ doesn't divide $\dfrac{n^2(n^2+1)}{2}$ for any $n \geq 3$ and the conclusion follows.

Note:1) Observe that if $n=2$, it is possible to obtain all the natural numbers from $1$ to $4$ with the above operations, since it is possible to increase any $1 \times 1$ square by any quantity. This accords with the fact that $1$ divides $1+2+3+4=10$ trivially.
2) Li Zhou gave a very clever solution to the general problem in which the entries of the $(n-1) \times (n-1)$ square are not changed by the same quantity (for example to the first entry add $1$, and to the other entries add $-1$ and so on). See the original solution published on Mathematical Reflections 3/2016.