[seqfan] Re: Alternating Vertical and Horizontal Moves In Grid

David Wilson dwilson at gambitcomm.com
Wed Feb 25 23:33:00 CET 2009

It seems fairly clear to me that starting anywhere gives:

a(n) = 1, if n = 1
n^2-n+2 if n even
n^2-2n+4 if n odd > 1

and starting in the corner is

a(n) = 1, if n = 1
n^2-n+2 if n even
n^2-2n+3 if n odd > 1

It would probably not be too hard to establish that these are lower 
bounds. For example, in


the figures for sides 4, 6, 8, 10 and 12 are spiral paths. Indeed, if 
you turn the pictures for sides 2(not shown), 4, 6, 8 and 10 upside 
down, you get the lower right corners of the pictures for sides 4, 6, 8, 
10 and 12, respectively, and that extending the side n path to the side 
n+2 path introduces 2 unvisited squares. This can be massaged into a 
proof that the 2n side square has at most n-2 unvisited squares, giving 
a path of at least n^2-n+2 squares.

The difficult part is proving you can do no better. I suspect you can 
show that the optimal path must have a minimal number of bends, and that 
each bend must have an associated unvisited square.

In the images, the odd-side squares have more erratic paths, but I am 
guessing a pattern might be established for them as well.

More information about the SeqFan mailing list