1 Hugo plays a game: he places a chess piece on the top left square of a $20 \times 20$ chessboard and makes 10 moves with it. On each of these 10 moves, he moves the piece either one square horizontally (left or right) or one square vertically (up or down). After the last move, he draws an $\mathrm{X}$ on the square that the piece occupies. When Hugo plays this game over and over again, what is the largest possible number of squares that could eventually be marked with an $\mathrm{X}$ ? Prove that your answer is correct.
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.
Note that if the chessboard is colored black and white in the usual way with a black square in the top left corner, then these squares are the top left square together with the next 5 black diagonals that run from the left side to the top of the board.