Q4 Matemática  (IberoAmerican 2006)

Os números $1,2,\dots ,n^2$ são escritos nos quadrados de um tabuleiro $n\times n$ em alguma ordem. Inicialmente há uma ficha no quadrado marcado com $n^2.$ Em cada passo, a ficha pode ser movida para qualquer quadrado adjacente (ao lado). No início, o token é movido para o quadrado rotulado com o número $1$ ao longo de um caminho com o número mínimo de etapas. Em seguida, ele é movido para o quadrado marcado com $2,$ e depois para o quadrado $3,$ etc, sempre pelo caminho mais curto, até retornar ao quadrado inicial. Se a viagem total levar $N$ passos, encontre o menor e o maior valor possível de $N.$