Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
The previous edition of this problem has now been posted to MO, mathoverflow.net/questions/88659/… –  Gerry Myerson Feb 16 '12 at 22:31

1 Answer 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.

share|improve this answer
2  
Good, but atleast two non-decreasing paths exist, eg by spiraling, possibly they are unique –  user1708 Feb 13 '12 at 18:23
    
Yes, thus the "almost". –  Henning Makholm Feb 13 '12 at 18:26
    
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... –  Steven Stadnicki Feb 13 '12 at 18:29
3  
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}$. –  Gerry Myerson Feb 14 '12 at 1:07
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. –  Henning Makholm Feb 14 '12 at 16:03

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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