[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
http://ilex.iit.cnr.it/resta/Leroy2.pdf
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