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$?

  • 1
    The previous edition of this problem has now been posted to MO, http://mathoverflow.net/questions/88659/traversing-the-infinite-square-grid2012-02-16

1 Answers 1

1

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.

  • 2
    @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.2012-02-14