Question 15
The numbers $1$, $2$, $3$, ..., $n^2$ are placed in the cells of a $n \times n$ grid, in some order, one number per cell. A token is initially found in the space with the number $n^2$. At each step, the piece can advance to any of the squares that share a side with the square it is on. First, the token travels to the square with the number $1$, and to do so it takes one of the shortest paths (with fewer steps) between the square with the number $n^2$ and the square with the number $1$. From the square with the number $1$ it travels to the square with the number $2$, from there to the square with the number $3$, and so on, until it returns to the initial square, taking the shortest path on each of its trips. The complete path takes the $N$ tab steps. Determine the smallest and largest possible value of $N$.