11.3. Given a natural number $k$. On a grid plane, $N$ cells are initially marked. We will call the cross of cell $A$ the set of all cells that are in the same vertical or horizontal line with $A$. If the cross of an unmarked cell $A$ contains at least $k$ other marked cells, then cell $A$ can also be marked. It turned out that by a chain of such actions, any cell on the plane can be marked. For what smallest $N$ could this have happened? (G. Chelnokov)
Answer. $N=\left[\frac{k+1}{2}\right] \cdot\left[\frac{k+2}{2}\right]=\left\{\begin{array}{ll}m(m+1), & \text { if } k=2 m ; \\ m^{2}, & \text { if } k=2 m-1\end{array}\right.$.

Solution. Let $N(k)$ be the answer to the problem; set $f(k)=\left[\frac{k+1}{2}\right] \cdot\left[\frac{k+2}{2}\right]$. First, we prove that

$$
N(k) \geqslant N(k-1)+\left[\frac{k+1}{2}\right] \quad \text { for } k \geqslant 2 .
$$

After marking the initial $N(k)$ cells, we can mark at least one cell $A$; this means that either in the column or in the row of this cell, there are already $\left[\frac{k+1}{2}\right]$ other marked cells—let's assume for definiteness in row $\ell$.

We mentally mark all the cells in row $\ell$. It is clear that any cell can still be marked. Remove row $\ell$ from the grid and shift the two resulting half-planes together so that a grid is formed again. Now, we can mark any cell in this new plane, marking on each step a cell in whose cross there are already at least $k-1$ marked cells (since one cell from row $\ell$ has been removed from this cross). Therefore, initially, there must have been at least $N(k-1)$ marked cells on this plane. This means that on the original plane, there should have been at least $N(k-1)$ marked cells not from $\ell$; hence, $(*)$ follows.

Since $N(1)=1$, from the proven inequality $(*)$ it follows that

$$
N(k) \geqslant \underbrace{1+1+2+2+3+3+4+\ldots}_{k \text { terms }}=f(k) \text {. }
$$

![](https://cdn.mathpix.com/cropped/2024_05_06_279a926c4d6807b68603g-04.jpg?height=614&width=618&top_left_y=660&top_left_x=436)

Fig. 16

It remains to show how to mark $f(k)$ cells so that any other cell on the plane can then be marked. We show by induction that the example shown in Fig. 16, consisting of two "staircases" of heights $p=\left[\frac{k}{2}\right]$ and $q=\left[\frac{k+1}{2}\right]$, works; it is not hard to see that it contains exactly $f(k)$ cells. For $k=1$, the statement is obvious: with one marked cell, any cell in its cross can be marked, and then any cell in general.

For the inductive step, note that cells $a_{1}, a_{2}, \ldots, a_{p}$ can be marked sequentially. After this, in the row they are in, there will be $p+q=k$ cells, and any cell in this row can already be marked. Therefore, by removing this row, the value of $k$ can be reduced by 1, and the inductive hypothesis can be applied to the remaining plane.