We need to write a positive integer in each cell of an infinitely large square grid paper under the following conditions. The number $n$ should appear exactly $n$ times (that is, one 1, two 2s, etc., should appear on the paper), and the difference between any two numbers in adjacent cells should be less than a given $k$. What is the smallest integer $k$ for which the filling can be completed?
First, we show that the sought $k$ is at least 3. The cell containing the one shares an edge with four other cells, while the paper only contains two twos. Thus, a number greater than two must be placed in one of the adjacent cells, so their difference is at least 2.

Next, we show that the filling can be carried out for $k=3$. We divide the paper into two half-planes with a straight line of the square grid. We write only odd numbers in the cells of one half-plane and only even numbers in the cells of the other half-plane. We place the one and the twos along the boundary line, so that the cell containing one of the twos shares an edge with the cell containing the one and also with the cell containing the other two. We write threes above and next to the one, fives above and next to the threes, and so on (Figure 1).

![](https://cdn.mathpix.com/cropped/2024_05_02_32b61c586941403eab76g-1.jpg?height=838&width=786&top_left_y=519&top_left_x=651)

We proceed similarly with the placement of even numbers in the other half-plane.

In the crescent-shaped layers containing the same numbers, the numbers are always two greater than in the preceding layers, and the number of numbers in each layer increases by two. Thus, if we start with one one and two twos, any positive integer $n$ will occur exactly $n$ times. It follows from the method of filling that the difference between the numbers in cells sharing an edge within one half-plane is 2 or 0. The numbers in cells sharing an edge from different half-planes are adjacent. The described filling thus meets the conditions of the problem.

![](https://cdn.mathpix.com/cropped/2024_05_02_32b61c586941403eab76g-1.jpg?height=775&width=773&top_left_y=1721&top_left_x=665)

Figure 2

|  |  |  | 7 |  |  |  |  |
| :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- |
|  |  | 6 | 5 | 7 |  |  |  |
|  | 6 | 4 | 3 | 5 | 7 |  |  |
| 6 | 4 | 2 | 1 | 3 | 5 | 7 |  |
| 7 | 5 | 3 | 2 | 4 | 6 |  |  |
|  | 7 | 5 | 4 | 6 |  |  |  |
|  |  | 7 | 6 |  |  |  |  |
|  |  |  |  |  |  |  |  |

Gábor Papp (Budapest, Móricz Zs. Gymnasium, 3rd grade)

Note. It can be shown that for $k=3$, every valid filling can be derived from the fillings shown in Figures 1-3 by reflection, $90^{\circ}$ rotation, and translation.