MathDB

The numbers

1,\, 2,\, \ldots\, , n^{2}

are written in the squares of an

n \times n

board in some order. Initially there is a token on the square labelled with

n^{2}.

In each step, the token can be moved to any adjacent square (by side). At the beginning, the token is moved to the square labelled with the number

1

along a path with the minimum number of steps. Then it is moved to the square labelled with

2,

then to square

3,

etc, always taking the shortest path, until it returns to the initial square. If the total trip takes

N

steps, find the smallest and greatest possible values of

N.

Problem Statement