A token is placed in one square of a $m\times n$ board, and is moved according to the following rules: In each turn, the token can be moved to a square sharing a side with the one currently occupied. The token cannot be placed in a square that has already been occupied. Any two consecutive moves cannot have the same direction. The game ends when the token cannot be moved. Determine the values of $m$ and $n$ for which, by placing the token in some square, all the squares of the board will have been occupied in the end of the game.
Problem
Source:
Tags: combinatorics proposed, combinatorics
mavropnevma
30.05.2010 14:13
The problem asks to find a Hamiltonian path, made of orthogonal unitary edges, on a $m \times n$ grid. Clearly this is possible if $m$ or $n$ is equal to $2$ - just start in a corner and make the mandatory moves allowed. If one of $m$ or $n$ is equal to $1$, it is trivial the other one must also be $1$, or $2$ (included in the above). If both $m$ and $n$ are larger than $2$, such a path will have to pass through a corner, but just look what happens! the second to last square before entry and the second square after exit will have to coincide, absurd. Therefore the only such boards are $1 \times 1$, $2 \times N$ and $N \times 2$, for any $N \geq 1$.
peregrinefalcon88
19.06.2010 21:37
It is easy to see that you must end in a 2 by 2 box in a corner and so u must start in a corner. Also in the starting 2 by 2 box and ending 2 by 2 box there should be 2 corners in order to cover all corner which gives us n or m =2 or m=n=1.