An array $n \times n$ is given, consisting of $n^2$ unit squares. A pawn is placed arbitrarily on a unit square. A move of the pawn means a jump from a square of the $k$th column to any square of the $k$th row. Show that there exists a sequence of $n^2$ moves of the pawn so that all the unit squares of the array are visited once and, in the end, the pawn returns to the original position.
Problem
Source: Balkan MO ShortList 2008 C4
Tags:
06.04.2020 09:50
We induct on $n \geq 1$, with the result being obvious for $n=1$. Suppose such a strategy exists for a $(n-1) \times (n-1)$ array. Now consider a $n \times n$ array. It suffices to show that there exists such a sequence of moves for any one position of the pawn. So assume that the pawn is initially placed in the top-left cell. Apply the inductive strategy on the top-left $(n-1) \times (n-1)$ sub-array (it's easy to see that we can do so). But at the last step, instead of going back to the initial position, stop the pawn. Note that, at this instant, the pawn must be in the $1^{\text{st}}$ column (since it finally has to reach the $1^{\text{st}}$ row). Now, when we have to take the pawn to a cell on the first row, instead of taking it to $(1,1)$ (which is the initial position of the pawn), take it to $(1,n)$. Now, we are in the last column, so the pawn has to go to the last row. We command the pawn to go to $(n,2)$, i.e. the second cell of the last row. Then jump it over to $(2,n)$. Then take it to $(n,3)$, and continue in this manner. At the end, we would have covered all cells of the last row, except for the first square, and the whole last column. Also, the pawn would be at $(n,n)$. Since we are in the $n^{\text{th}}$ column, so we take the pawn to $(n,1)$ (which we had left empty initially). Finally, we are again in the first column, and so we can jump over to $(1,1)$ (i.e. the starting position). In this way, we have a sequence of moves which covers all squares exactly once, and takes the pawn back to its starting position. $\blacksquare$
06.04.2020 16:41
Bulgaria TST 2008