10.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.

![](https://cdn.mathpix.com/cropped/2024_05_06_be662655670e424b8d07g-02.jpg?height=497&width=434&top_left_y=131&top_left_x=857)

Fig. 10 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$.

Mentally mark all 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_be662655670e424b8d07g-03.jpg?height=614&width=620&top_left_y=428&top_left_x=433)

Fig. 11

It remains to show how to mark $f(k)$ cells so that any other cell on the plane can then be marked. We will show by induction that the example shown in Fig. 11, 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.