What is the least possible number of cells that can be marked on an $n \times n$ board such that for each $m>\frac{n}{2}$ both diagonals of any $m \times m$ sub-board contain a marked cell?

## Answer: $n$.
For any $n$ it is possible to set $n$ marks on the board and get the desired property, if they are simply put on every cell in row number $\left\lceil\frac{n}{2}\right\rceil$. We now show that $n$ is also the minimum amount of marks needed.

If $n$ is odd, then there are $2 n$ series of diagonal cells of length $>\frac{n}{2}$ and both end cells on the edge of the board, and, since every mark on the board can at most lie on two of these diagonals, it is necessary to set at least $n$ marks to have a mark on every one of them.

If $n$ is even, then there are $2 n-2$ series of diagonal cells of length $>\frac{n}{2}$ and both end cells on the edge of the board. We call one of these diagonals even if every coordinate $(x, y)$ on it satisfies $2 \mid x-y$ and odd else. It can be easily seen that this is well defined. Now, by symmetry, the number of odd and even diagonals is the same, so there are exactly $n-1$ of each of them. Any mark set on the board can at most sit on two diagonals and these two have to be of the same kind. Thus, we will need at least $\frac{n}{2}$ marks for the even diagonals, since there are $n-1$ of them and $2 \nmid n-1$, and, similarly, we need at least $\frac{n}{2}$ marks for the the odd diagonals. So we need at least $\frac{n}{2}+\frac{n}{2}=n$ marks to get the desired property.

#