An *m*×*n* grid is filled with the integers from 1 to *mn*
(inclusive) in any order. A marker is placed on the square containing 1. It is
then moved to the square containing 2 via adjacent squares (squares sharing an
edge) in the fewest moves possible. It is then moved to the square containing 3
under the same restrictions, etc. When it reaches the square containing *mn*
it then returns to the square containing 1 (with the usual restrictions).

For example, when *m* = *n* = 3, a trip on the square on the left in the
figure below, has stages of length 1, 1, 2, 3, 2, 3, 2, 3, 1 for a total of
18 steps. The square on the right has stages of length 1, 2, 1, 1, 2, 1, 2, 1, 1
for a total of 12 steps.

For given *m* and *n*, what is the shortest possible total trip length
and what is the longest?

**
The solution will be posted shortly.
**

Back to the Archives

Back to the Math Department Homepage.