Starting somewhere on an infinite square grid, is it possible to visit every square exactly once, if at move $n$, one must jump $a_n$ steps in one of the directions north,south,east or west, and mark the ending square as visited?
If $a_n=n$ or if $a_n=n^2$?
Allowing diagonal moves as well, is there a general algorithm, given $a_n$, to check if a path exists?
Note:
I am asking if given $a_n$, there exists an infinite sequence of directions, $d_n\in(N,S,W,E)$, such that for all $(x,y)\in Z^2$, there exists a finite integer $k(x,y)$, such that starting at the unit square with center $(0.5,0.5)$, marked as visited, we have after moving sequentially $a_i$ steps in direction $d_i$, for $i=1,2,3,…,k$, visited $k+1$ different unit squares, and are situated at $(x+0.5,y+0.5)$.
Best Answer
It's possible for $a_n=n$ and probably most stepsizes without modular or growth obstructions.
We have covered some subset of an mxm square, are situated at the boundary, and want to visit a cell (x,y) in our square. Choose one of the x,y axes and move far away along it, (but not upon it), until stepsize s>>m and distance is some d from the axis. Then take either 1,2, or 4 more steps along the axis. Then alternately move away, and towards the axis, 2*d steps, until we land on it. Then by moving away and towards (x,y), n times, we can reach every point of the form j-1-3n on the axis, by just moving one more step towards (x,y) where j is our current coordinate, which we could shift to anything modulo 3 when we chose one of the 1,2,4 steps. And if 3n-n>m, we dont use any other squares within the the mxm square, to visit (x,y), and emerge on the opposit side. And since s>>m, if we take one more step we are at a boundary of a new square.
WLOG suppose we are at $(0,0)$, with stepsize $s(0)$, and want to visit $(x,y)$, $0\leq x\leq m$, $0\leq y \leq m$, The full path we take consist of these moves. We move south for $k$ squares (or $j(k)$ steps), then alternate west,east, $x$ times, now we are at $(x,-k)$ with stepsize $s(j(k)+2x)$. Then we alternate south, east, $n$ times, now we are at $(x,n-k)$ with stepsize $s(j(k)+2x+2n)$, select $n$ and $k$ such that $y=s(j(k)+2x+2n)+n-k$ and $s(j(k)+2x+2n)>m$. Then take two steps north, we are now at $(x,y+s(j(k)+2x+2n)+1)$. Move 1 step east, you are now at a corner of a square bounding all visited squares, define the new m to be the side of this new square, let (0,0) your position, pick a new point (x,y) and repeat.
PS. I asked a question about the less trivial 1-D version here: https://math.stackexchange.com/questions/111377/self-avoiding-walk-on-mathbbz