7
$\begingroup$

Suppose we start at $(0.5,0.5)$ in an infinite unit square grid, and our goal is to traverse every square on the board.

At move $n$ one must take $a_n$ steps in one of the directions, north,south, east or west. And every square we walk over is marked as visited, we are not allowed to walk over a visited square twice.

Is there a sequence of directions, such that we can visit every square of the board exactly once if $a_n=n$?

Is there such a sequence if we are allowed to walk in diagonal directions aswell?

Is there a general algorithm to check, given $a_n$, if a path exists?

Is there a path in any of the above cases for $a_n=n^2$?

$\endgroup$
1
$\begingroup$

If your $a_n$ are increasing, this is always impossible.

Suppose (by symmetry) that you start by going south. Sooner or later you will have to move north. However, after your first north move, you'll have drawn an U shape of width $a_i$ on the grid, and there will be no way for you later to enter the interior of the U from the north and get back up again without having an $a_j$ available that is at most $a_i-2$.

This argument also almost shows that it is impossible with a merely non-decreasing sequence of $a_n$'s.

Things appear to be more murky if diagonal moves (like bishops in chess) are allowed.

$\endgroup$
  • 2
    $\begingroup$ Good, but atleast two non-decreasing paths exist, eg by spiraling, possibly they are unique $\endgroup$ – TROLLHUNTER Feb 13 '12 at 18:23
  • $\begingroup$ Yes, thus the "almost". $\endgroup$ – hmakholm left over Monica Feb 13 '12 at 18:26
  • $\begingroup$ The question also looks to become much more interesting if cells along the way aren't marked 'visited', only the cell at the end of each step... $\endgroup$ – Steven Stadnicki Feb 13 '12 at 18:29
  • 3
    $\begingroup$ Why width $a_i$? Maybe you started out going south, then went $a_i$, $a_{i+1}$, $a_{i+2}$ west before turning north. The width of the U is then $a_i+a_{i+1}+a_{i+2}$. $\endgroup$ – Gerry Myerson Feb 14 '12 at 1:07
  • 2
    $\begingroup$ @Gerry: That's a really good point. However, if the $a$s are increasing then the first time you get into the U you have to use fewer moves east/west at the bottom, so we can patch up the proof by induction on the number of moves in the horizontal segment. $\endgroup$ – hmakholm left over Monica Feb 14 '12 at 16:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.