, 2021

Solution:

In this solution, we will reference cells by row and column, measured from left to right and top to bottom. The cell at $(0,0)$ is then in the top-left corner; the cell at $(1,3)$ is in the fourth cell of the second row.

For $n=1$, we can mark the sole cell.

For $n=p$, where $p$ is a prime, we need only ensure that each $1 \times n$ and $n \times 1$ rectangle contains a mark. This is the same as ensuring that all rows and columns contain a mark, which can be done, for example, by marking all cells $(k, k)$ for integers $k \in[0, n)$.

For $n=p^{2}$, there must be a mark in each row and column and also in each $p \times p$ rectangle. To achieve this, we can mark all cells of the form $(j+k p, k+j p)$, for integers $j, k \in[0, p)$. An illustration for $n=9$ follows:

Note that there are exactly $p^{2}=n$ such cells, and that row $r$ contains a cell in the column
$$\left\lfloor\frac{r}{p}\right\rfloor+(r \bmod p) \cdot p$$
Likewise, there is a marked cell in each column. Now, we will show that all $p \times p$ rectangles contain a marked cell. Consider the rectangle $R$ with upper-left corner at $(x p+y, z)$ for integers $x, y \in[0, p), z \in [0, n)$. Then, if $z>x+(y-1) p, R$ contains the cell
$$\left(x p+\left\lceil\frac{z-x}{p}\right\rceil, x+\left\lceil\frac{z-x}{p}\right\rceil p\right)$$
and otherwise it contains the cell
$$\left((x+1) p+\left\lfloor\frac{z-x}{p}\right\rfloor, x+\left\lfloor\frac{z-x}{p}\right\rfloor p+1\right) .$$
Since $z \leq n-p$, this cell is always a valid marked cell. This concludes the proof that the construction is correct.

Now, we prove that no other values of $n$ are satisfiable. First, we again note that every row and column must have exactly one marked cell, as there are $n$ of each and they are disjoint. Let $n=a b$ for $1<a, b<n$ and partition the $n \times n$ grid into a $b \times a$ grid of $a \times b$ rectangles. In particular, let $R_{i j}$ be the rectangle that has upper-left corner at $(b i, a j)$ and lower-right corner at $(b i+b-1, a j+a-1)$ for $i \in[0, a), j \in[0, b)$. Then each $R_{i j}$ must contain exactly one marked cell, since there are also $n$ of them and they are disjoint.

Consider the set of rectangles $R_{i 0}$. There are exactly $a$ marked cells among these rectangles - one in each of the columns from $0$ to $a-1$, and also one in each of the $a$ rectangles $R_{i 0}$. Therefore, there is some permutation $X$ of the integers $[0, a)$ so that $R_{i 0}$ has a marked cell in column $X_{i}$. Now, we will prove the claim that if a rectangle $R_{i j}$ contains a marked cell in column $c$ of the grid, $c \equiv X_{i}(\bmod a)$. We prove this by induction on $j$, having already demonstrated the case $j=0$. Suppose the claim holds for some $j$; we will show it must also hold for $j' = j+1$. Consider $k$ satisfying $X_{k}=0$. We know that the unique marked cell in rectangle $R_{k j}$ is in column $a j$. Therefore, $R_{k j'}$ must contain a mark in column $a j+a$, as otherwise the $a \times b$ rectangle with top-left corner at $(b k, a j+1)$ has no mark. Next, consider $k'$ satisfying $X_{k}=1$. The unique marked cell in rectangle $R_{k' j}$ is in column $a j+1$. Also, the rectangle $R_{k' j'}$ cannot contain a marked cell in column $a j+a$, since there is already a mark in that column. So $R_{k' j'}$ must contain a marked cell in column $a j+a+1$, as otherwise the $a \times b$ rectangle with upper-left corner at $(b k, a j+2)$ has no mark. Proceeding in order of increasing $X_{i}$ in this way forces the claim to hold for $k'$ as well, completing the inductive proof.

Likewise, there is a permutation $Y$ of the integers $[0, b)$ so that, if $R_{i j}$ contains a marked cell in row $r$ of the grid, $r \equiv Y_{j}(\bmod b)$.

We will now show that either $X$ and $Y$ are both increasing or both decreasing. Suppose not, so that for some $i, j, X_{i}>X_{i+1}$ and $Y_{j}<Y_{j+1}$ (or the same with $X, Y$ swapped, which is handled identically). Then, consider the rectangles $R_{i j}, R_{(i+1) j}, R_{i(j+1)}$, and $R_{(i+1)(j+1)}$. An example for $n=6$ follows:

Taking an $a \times b$ rectangle with upper-left corner directly below the marked cell in $R_{i j}$, we find that it lies entirely inside these four rectangles and yet does not contain any of their marked cells. In particular, we can note that, since $Y$ is increasing at this point, the horizontal distance between the marks in the lower left and upper right is strictly greater than $a$. Also, since $X$ is decreasing at this point, the vertical distance between the marks in the top left and lower right is strictly greater than $b$. This means that an $a \times b$ rectangle with no mark exists, a contradiction. Therefore, either $X$ is increasing or $Y$ is decreasing.

Suppose, without loss of generality, that both are increasing (noting that the increasing and decreasing cases are simply $90^{\circ}$ rotations of each other). Then the marked cell in row $1$ must be $a+1$. But if $n$ is divisible by two distinct primes or the cube of a prime, there is no unique value for $a$, which is a contradiction. Therefore, $n$ must be $1$, a prime, or the square of a prime.