Font der Flasch D:

A square board is divided by a grid of horizontal and vertical lines into $n^{2}$ cells with a side length of 1. For what largest $n$ can $n$ cells be marked so that every rectangle of area at least $n$ with sides along the grid lines contains at least one marked cell?
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 \times 7$ board that satisfies the condition of the problem is shown in the figure.

![](https://cdn.mathpix.com/cropped/2024_05_06_0ff1ee02df212bd75258g-12.jpg?height=234&width=234&top_left_y=2101&top_left_x=912)

## Answer

For $n=7$.