Question 62
Let $n$ be a natural number. A sequence $x_1, x_2, \dots, x_{n^2}$ is called *n-*good if each $x_i$ is an element of $\{1, 2, \dots, n\}$ and the ordered pairs $(x_i, x_{i+1})$ are all different for $i = 1, 2, \dots, n^2$ (here we consider the subscripts modulo $n^2$). Two *n-*good sequences $x_1, x_2, \dots, x_{n^2}$ and $y_1, y_2, \dots, y_{n^2}$ are called *similar* if there exists an integer $k$ such that $y_i = x_{i+k}$ for all $i = 1, 2, \dots, n^2$ (again taking the subscripts modulo $n^2$). Suppose that there exists a non-trivial permutation $\sigma$ of $\{1, 2, \dots, n\}$ and an *n-*good sequence $x_1, x_2, \dots, x_{n^2}$ which is similar to $\sigma(x_1), \sigma(x_2), \dots, \sigma(x_{n^2})$. Show that $n \equiv 2 \pmod{4}$.