IrMO 2012 Problem 10

Let $n$ be a positive integer. A mouse sits at each corner point of an $n\times n$ board, which is divided into unit squares as shown below for the example $n=5$ .

The mice then move according to a sequence of steps, in the following manner:

(a) In each step, each of the four mice travels a distance of one unit in a horizontal or vertical direction. Each unit distance is called an edge of the board, and we say that each mouse uses an edge of the board.

(b) An edge of the board may not be used twice in the same direction.

(c) At most two mice may occupy the same point on the board at any time.

The mice wish to collectively organize their movements so that each edge of the board will be used twice (not necessarily be the same mouse), and each mouse will finish up at its starting point. Determine, with proof, the values of $n$ for which the mice may achieve this goal.