4. Let $n$ be a natural number. Determine (in terms of $n$) the smallest natural number $m$ for which it is possible to color exactly $n$ cells of an infinite square grid such that the following condition holds:

- Every rectangle with sides along the grid lines, whose two opposite corners are colored, contains at most $m$ colored cells.

Time for work: 270 minutes.

Each task is worth 10 points.
4. The answer is $m=1$ for $n=1$ and $m=\left[\frac{n}{5}\right]+2$ for $n \geqslant 2$.

Consider the smallest rectangle $\mathcal{P}$ with sides along the lines that contains all the colored cells. It has at least one colored cell along each of its sides. We select colored cells $A, B, C$ and $D$ along the bottom, right, top, and left sides of the rectangle $\mathcal{P}$. For $n \geqslant 2$, we can take $A \neq C$ and $B \neq D$ (but it can be, for example, $A=B$). With $\mathcal{P}_{X Y}$ we denote the rectangle whose two opposite corner cells are $X$ and $Y$. Then the rectangles $\mathcal{P}_{A B}, \mathcal{P}_{B C}$, $\mathcal{P}_{C D}, \mathcal{P}_{D A}$ and $\mathcal{P}_{A C}$ together contain all $n$ colored cells. At the same time, cells $A$ and $C$ are in three of these five rectangles, and cells $B$ and $D$ are in two. It follows that $5 m-6 \geqslant n$, i.e., $m \geqslant\left[\frac{n}{5}\right]+2$.

To show that this estimate is achievable, it is sufficient to construct an example for $n=5 k+4$ and $m=k+2$, where $k \geqslant 0$ is an integer. One possibility is shown in the figure. Indeed, any rectangle that contains some colored cells of the central $k \times k$ square (of which there are $k$) can contain at most two more colored cells, while any other rectangle can contain at most $k+1$ colored cells from one square of side $k+1$ and one more from

![](https://cdn.mathpix.com/cropped/2024_06_04_fe9d2507d114d9e8bcdbg-3.jpg?height=536&width=534&top_left_y=382&top_left_x=1206)
another such square.

![](https://cdn.mathpix.com/cropped/2024_06_04_fe9d2507d114d9e8bcdbg-3.jpg?height=474&width=54&top_left_y=440&top_left_x=1708)