Evaluation. It is clear that if $n$ cells are marked in such a way that the condition of the problem is satisfied, then in each row and each column there is exactly one marked cell. Assuming that $n \geq 3$ (it is obvious that $n=2$ is not the largest), let's take row $A$, in which the leftmost cell is marked, row $B$, adjacent to $A$, and row $C$, adjacent either to $A$ (and not coinciding with $B$) or to $B$ (and not coinciding with $A$). Let $b$ be the number of the marked cell in row $B$. If $b \leq n-\left[\frac{n+1}{2}\right]$ or $b \geq\left[\frac{n+1}{2}\right]+2$, then in rows $A$ and $B$ there will be a rectangle of area not less than $n$ that does not contain marked cells, hence $b \leq n-\left[\frac{n+1}{2}\right]$. Consider two rectangles formed by the intersection of rows $A, B$ and $C$ with columns numbered $2,3, \ldots, n-\left[\frac{n+1}{2}\right]$ and columns numbered $2+\left[\frac{n+1}{2}\right], \ldots, n$. These rectangles do not contain the marked cells of rows $A$ and $B$. If $n > 7$, then the area of each of them is not less than $n$, but row $C$ contains only one marked cell, which means that one of these rectangles does not contain marked cells. Therefore, $n \leq 7$.

An example of a 7×7 board satisfying the condition of the problem is shown in the figure.

![](https://cdn.mathpix.com/cropped/2024_05_06_49e49f22191b45b40a57g-37.jpg?height=245&width=240&top_left_y=1804&top_left_x=912)

## Answer

For $n=7$.
$\underline{\text { Fon-err-Flaass problem: }}$

A square board is divided by a grid of horizontal and vertical lines into $n^{2}$ unit squares. For what largest $n$ can one mark $n$ cells so that every rectangle of area at least $n$ with sides along the grid lines contains at least one marked cell?