[seqfan] Nonoverlapping, increasing paths in nXn grids

[Charles Greathouse]

Inspired by (warning: math education)
http://www.youtube.com/watch?v=ZNmstUbD-pA
I decided to look for the sequence of maximal nonoverlapping increasing
paths in 2X2, 3X3, ... grids. I'm having trouble searching, though; this
problem is hard to brute force. In fact I could find only three terms: a(1)
= 0, a(2) = 2, a(3) = 4. A160663 gives an upper bound but I'm not sure how
closely it can be approached.

For example, the best you could hope for in the 2X2 case is a step of 1
followed by a step of sqrt(2), which is easily accomplished. In 3X3 you
might hope for 1, sqrt(2), 2, sqrt(5), then 2sqrt(2). But once you take a
step of 2sqrt(2) across the main diagonal, you have only one choice to get
a distance of sqrt(5) [well, one on either side, but only one
symmetry-reduced choice], at which point there are no options for a step of
length 2. But 4 can be accomplished easily; numbering the grid
top-to-bottom, left-to-right 1 through 9 sequence 1--4--2--8--3 gives four
distinct distances.

Is this sequence in the OEIS? Does it have a name?

Charles Greathouse
Analyst/Programmer
Case Western Reserve University