Problem 1958

Solution:

Index each square by its row number and column number, starting with $0$. For example, $(0,0)$ represents the top left square and $(2,5)$ represents the square in the third row down and the sixth column over. When the piece moves down or to the right, the sum of the indices of its square increases by $1$, and when the piece moves up or to the left, this sum decreases by $1$. Since it starts on a square with sum of indices $0$, after $10$ moves it must lie on a square with sum of indices at most $10$. In addition, since each move changes the sum of indices from even to odd or from odd to even and the piece starts on a square with an even sum of indices, after an even number of moves the sum of indices must be even. Therefore, after $10$ moves, the piece lies on a square whose sum of indices is an even number $\leq 10$.

It is possible to reach any one of the squares with sum of indices an even number $\leq 10$ at the end of $10$ moves, since the piece can get to the square $(i, j)$ with $i+j \leq 10$ simply by moving $i$ squares down, then $j$ squares to the right. If $i+j=10$, this uses up all $10$ moves; otherwise, the piece can waste the remaining $10-i-j$ moves (which is an even number of moves since $i+j$ is even) simply by moving the piece down a square and then up a square until $10$ moves are reached.

We have shown that the squares that could be marked with an $\mathrm{X}$ are the squares of indices $(i, j)$ where $i+j$ is an even number $\leq 10$. Since the squares with $i+j=n$ form a diagonal of length $n+1$ extending from the left side of the board to the top of the board, there are $1+3+5+7+9+11=36$ such squares.