Is it possible to arrange everything in all cells of an infinite checkered plane all natural numbers (once) so that for each $n$ in each square $n \times n$ the sum of the numbers is a multiple of $n$?
Problem
Source: St. Petersburg 2019 10.6
Tags: combinatorial geometry, combinatorics, positive integers, Chessboard, infinite chessboard
Pathological
02.05.2019 06:38
is yes.
We'll describe an algorithm to produce such a labelling. First let's assign a labelling $\mathbf{Z}^2$ to the checkered plane in the obvious way. Let $S_i$ denote the set of $(x, y) \in \mathbb{Z}^2$ with $|x| + |y| = i,$ for any given $i \in \mathbb{Z}_{\geq 0}.$ Then, our algorithm will proceed to label $S_0,$ then $S_1,$ then $S_2,$ etc. Firstly, it will write $1$ at $(0, 0),$ hence filling up $S_0.$ Now, for each $i,$ we will fill $S_i$ in "clockwise" fashion, starting with the filling of $(i, 0),$ continuing to $(i-1, -1),$ then to $(i-2, -2),$ etc. By the Chinese Remainder Theorem, we can always select a sufficiently large unselected positive integer for each of these cells by solving a system of congruence equations.
A way to show this would be to observe that there is some positive integer $n$ such that the square we are currently trying to fill is contained only in the squares for which it is the top-right (WLOG assume this, the other cases are symmetric) corner. These squares comprise exactly one $1 \times 1$ square, exactly one $2 \times 2$ square, $\cdots$, and exactly one $n \times n$ square. Then, what we are going to do is that for each prime $p \le n$, we'll consider the largest power $p^k$ which is at most $n$. Then, we will consider the system of congruences only with the moduli of the form $p^k$ for each $p \le n$. Since the moduli are relatively prime, a solution must exist in this case. We will claim that any solution here is a solution to all $n$ equations. Indeed, if $p^k$ divides $n$, then we can tile the $n \times n$ square with $p^k \times p^k$ squares, and so hence applying the condition on each of these squares gives that $p^k$ divides the sum of the $n \times n$.
Finally, since there are no restrictions for $(i+1, 0)$ other than divisibility by $1$, we can clearly just fill $(i+1, 0)$ with the smallest unselected positive integer. This will eventually ensure that every positive integer is selected once, so we're done.