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
Source: 21-st Iberoamerican Mathematical Olympiad
Tags: analytic geometry, combinatorics unsolved, combinatorics
cancer
11.07.2007 17:38
Anybody?
JBL
11.07.2007 22:23
For $ n$ even, the minimum is $ n^{2}$: we can make a complete circuit (e.g., start in upper-left corner, move down $ n-1$ times, right $ n-1$ times, up once, left $ n-1$ times and then repeat the circuit "up once, right $ n-1$ times, up once, left $ n-1$ times" $ \frac{n}{2}-1$ times). This is clearly minimal. For $ n$ odd, the minimum is $ n^{2}+1$. That this is a theoretical minimum follows from the fact that we must change colors every time we enter a new square and end where we began, so must make an even number of steps. It's not too hard to find paths which achieve this minimum. About the maxima, I have no idea.
skuge
23.08.2007 07:28
Minimum: The minimum is $ n^{2}$ for $ n$ even and can easely be achived. For $ n$ odd the minimum is $ n^{2}+1$ an the path is easely constructed. Maximum: Consider the lines between each column and line. In one step, the token crosses one (and only one) line. If a line separates the board in two boards of $ i\times n$ and $ (n-i)\times n$ ($ i\leq (n-i)$, can be crossed at most $ 2in$ times (one arriving to each square on the $ i\times n$ board and one living it). To achieve this maximum the token most cross the two middle lines in each turn. If $ n$ is odd this maximum can be obtained and the path is easy to obtain. If $ n$ is even the movement (across the two middle lines) restricts the token to move in only two of the four squares of $ \frac{n}{2}\times\frac{n}{2}$. In order to change this at least 2 movements most be "sacrificed". This new maximum can be obtain and the path can be constructed.
Ivob
30.04.2009 15:55
Although this is very old topic,i think i solved this one with other aproach. Maximum for n even is $ n^3 - 2$, and for n odd is $ (n - 1)*n*(n + 1)$ In each cell we wrote pair of numbers like in coordinate system. So,if we have point A with coordinates (e,f) and point B (g,h), then the minimum number of steps needed to come from point A to point B is |e-g| + |f-h|. And we now look what can be the maximum number of this sum. If anyone is interested in this old topic, then i could wrote the whole solution(actually i'll try to wrote ).