, 2023

Solution:

We claim the number of ways to select $n^{2}-1$ such cells from a $(2n-1) \times (2n-1)$ grid is exactly $n^{3}$, which implies the answer to this question is $1000$.

Partition the board into $n^{2}$ regions, as pictured. Also, shade red every cell in an odd row and column red, so there are $n^{2}$ red cells. Say a region is blank if it has no selected cell; normal if the selected cell is red; up-wack if the selected cell is above the red cell; and right-wack if the selected cell is to the right of the red cell. Note a $2 \times 2$ region could be both up-wack and right-wack.

The key idea is that we have at most one blank region, which restricts things significantly. We have two cases:

- Case 1: no wack regions. Then we pick a region to be blank, of which we have $n^{2}$ choices.

- Case 2: some wack region. Note that (1) any region directly above an up-wack region must be either blank or up-wack; and (2) any region directly to the right of a right-wack region must be either blank or right-wack. In particular, there is at most one wack region (and we cannot have any up-wack and right-wack regions), since every wack region corresponds to at least one blank region.

Suppose some region is up-wack. There are $n$ columns that could contain this up-wack region, and $\binom{n+1}{2}$ ways to pick an up-wack region and, optionally, a blank region above it. Similarly, there are $n\binom{n+1}{2}$ cases if there is some up-wack region, for a total of $2n\binom{n+1}{2}$ choices.

In total, we have $n^{2} + 2n\binom{n+1}{2} = n^{3}$ possibilities, as desired.