MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

Traversing the infinite square grid

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)$.

-
If $a_n=1$ for all $n$ then the answer is trivially yes (a spiral, for example). But if $a_n=2$ for all $n$, then I don't think it works. If you start at $(0,0)$ then you can only visit vertices $(x,y)$ where both $x$ and $y$ are divisible by 2. I'm not sure about $a_n=n$. I think it's an interesting question. – David White Feb 16 2012 at 20:18
Indeed, using a checkerboard coloring, the parity of the step size must be odd infinitely often, if the path is to take at most omega many steps. One can likely use to different colorings to get mod p results, and one can use arguments to show that exponential growth, and perhaps even polynomial growth for cubic and higher polynomials, also will skip some squares. Gerhard "Ask Me About System Design" Paseman, 2012.02.16 – Gerhard Paseman Feb 16 2012 at 20:34
I am inclined to say yes for a_n = n since given any two squares and any pattern generated by the first m steps, with the first square reached on the m+1st step, there is always a path to reach the second square which does not tread on any previous squares. A formal proof of the last statement should not be too hard to get, and the result should follow from it. I suspect a similar proof will hold for n^2, but will be harder to show. Gerhard "Ask Me About System Design" Paseman, 2012.02.16 – Gerhard Paseman Feb 16 2012 at 20:47
Actually, I retract that last comment. I see an idea which will lead to boxing in certain squares so that one cannot move from a square on the m+1 st step without treading on a previously visited square. Gerhard "Didn't Watch Where He Went" Paseman, 2012.02.16 – Gerhard Paseman Feb 16 2012 at 20:50
Originally posted to m.se, math.stackexchange.com/questions/108941/… – Gerry Myerson Feb 16 2012 at 22:31

[Sorry, I firstly misunderstood the question] Why not? Enumerate all squares. Assume that we have already visited some finite number of squares and are now placed in the boundary square (that is, one of its coordinates is either maximal or minimal between all visited squares). Say, in the upper square. Consider the square with minimal number, which is not visited yet. Our local goal is to visit it. For this we go to the up far-far away, then to the right, then to the down, and then to the left. So we have visited next square. Then go to the left and we are no in the leftmost square and number in it is also maximal.

I think, details are fairly simple at least in the case $a_n=n$. Indeed, if we go up by $+n$, $+(n+1)$, $+(n+2)$, \dots, $+(n+k)$ we increase y-coordinate by $n+\dots+(n+k)$. We could replace $+s$ to $-s$, then we would get $2s$ less sum. So, by choosing $k$ and $s$ (we may use not only one $s$, but say 2 or three different values of $s$, but do not choose two consecutive $s$) we may get all sufficiently large $y$-coordinates, making at most 2 or 3 down jumps. Moreover, even if $k$ is fixed we may get almost all coordinates of corresponding parity. Then we have the same freedom going to the right, then going down, and to the left. Choose parities and jumps to "opposite" directions for going to the necessary point.

For $a_n=n^2$ it should not be much harder.

-
The details here are certainly subtle, and omitting them does not lead to a satisfying answer. – Will Sawin Feb 18 2012 at 1:33
Such argument led to my initial comments above. Only later did I retract, when I saw how through lack of care I could box myself in. Gerhard "Ask Me About Incomplete Proof" Paseman, 2012.02.17 – Gerhard Paseman Feb 18 2012 at 2:03
How do you ensure that you don't hit a previously visited square while you go far away and come back? – Greg Martin Feb 27 2012 at 7:03
Reading your answer again and comparing to mmm's answer, it seems to me that your strategy could indeed lead to a solution (except maybe that in your first paragraph, I don't understand why you want to visit the "square with minimal number"). – François Brunault Feb 27 2012 at 16:58
@Greg: I start with the most Northern point and then go to North. Surely I do not visit previously visited squares. Then I go to East, then to South, and then to West and the first (and unique) square which is close enough to previosly visited which I visit during my walk is exactly the one which I need. – Fedor Petrov Mar 1 2012 at 9:42

For a one dimensional lattice, the solution with $a_n = n$ is trivial: starting from $0$, we proceed to $1, -1, 2, -2, \ldots$. After $2n$ steps, we have covered $[-n, n]$ without stepping anywhere outside of that region.

I'm not sure exactly what is meant by “traversing an infinite grid”, but I can think of two reasonable things one could ask for algorithmically: cover an $N \times N$ region for an arbitrary $N$ while hitting any number of spaces outside, or cover exactly an $N \times N$ region in $N^2$ steps.

The first method is accomplished by mimicking the one dimensional version. Suppose we want to cover the square with corners $(1,1)$ and $(N, N)$. Assume we start at $(0, 1)$, and move strictly horizontally, alternating east then west, to cover the squares $(-N + 1, 1)$ to $(N, 1)$, ending on the latter with a step of length $2N-1$. We then move east to $(3N, 1)$, then south $(3N, -2N)$, and back north to $(3N, 2)$. Now we proceed horizontally again, but perhaps not the obvious way. If we jumped back west into our desired square immediately, we would miss the spaces $(N-2, 2), (N-1, 2)$ and $(N, 2)$, and we may never see them again. So instead we go east, then jump back and forth until we have covered $(1, 2)$ to $(3N, 2)$, as well as $(5N + 3, 2)$ to $(8N+1, 2)$, ending at $(1,2)$ with a step of length $8N$. From here I suppose you see what to do: travel east, then south, then north, and repeat the sequence EWEW... ending at square $(N, 3)$. During leg $k$, we only hit squares in the horizontal line $y=k$, as well as one square at a negative $y$ value, which will never be reached again (consider the successive lengths of the steps south).

The second method cannot be done with $a_n = n$, since we will go outside the box sometime by step $N+1$. It may be possible instead with the set of $\lfloor \sqrt{n} \rfloor$ steps, though the order will have to be altered. For example, the sequence $(3,3,3,2,3,2,2,3,1,3,2,1,1,2,3)$ taken from the set $(\lfloor \sqrt{1} \rfloor, \ldots \lfloor \sqrt{15} \rfloor$ suffices to cover a $4 \times 4$ square, starting in one corner. From the southwest corner, travel $(N3, E3, S3, W2, N3, S2, E2, W3, N1, E3, W2, E1, S1, N2, S3)$ and you will finish one square west of the southeast corner.

-
I think the OP asks whether $\mathbf{Z} \times \mathbf{Z}$ (instead of $[1,N] \times [1,N]$) can be covered with no repetition, but your result is already interesting. – François Brunault Feb 18 2012 at 17:18

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: http://math.stackexchange.com/questions/111377/self-avoiding-walk-on-mathbbz

-
I'm not convinced by your argument. It seems to work for visiting one given cell, but when you repeat the process, how do you make sure the squares you need are free ? For example, you may need to use the same axis many more times. – François Brunault Feb 26 2012 at 21:54
@FrançoisBrunault All the original visited squares lie within the mxm square. We visit only one cell, (x,y) within the original mxm square. By alternating n times, we move n steps closer to the mxm-square, but the possible next step, moves 3*n, so if we moved far enough away initially then 3n-n>m, and we'd only need to step once inside the mxm square. – mmm – mmm Feb 27 2012 at 1:36
I agree with François. You are using squares outside the $m\times m$ part in order to visit one square inside it, but you don't seem to be counting those outside squares as being visited. But the way you stated your problem that doesn't seem to be allowed. How do you know that when you visit the next square inside the $m\times m$ part you won't need to use one of the squares outside it that you used before? – Brendan McKay Feb 27 2012 at 2:15
Ofcourse all squares count as visited. See my description of full path. NEXT TIME YOU INCREASE m to contain all cells, ofcourse. – mmm Feb 27 2012 at 11:53
@mmm. Thanks for the edit. Your proof seems correct and I now understand your idea of making the stepsize arbitrarily large in order to make the induction work. This is a quite nice and surprising result ! – François Brunault Feb 27 2012 at 12:51