Problem

Source: Balkan MO ShortList 2008 C4

Tags:



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.