[seqfan] Re: Nonoverlapping, increasing paths in nXn grids

[Giovanni Resta]

On 06/13/2013 08:22 AM, Charles Greathouse wrote:
> 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.

Unless I've made mistakes (testing the crossing was a little tricky for 
me) I have computed the sequence up to a(8).
This is assuming that the path does not touch itself not even on
single points.
I got: 0,2,4,7,9,12,15,17

it is interesting to note that for a(4), a(6) and a(7) starting
from a corner does not give the best solution. a(9) is at least 20.
The solutions for a(7)=15 and a(8) are
----------------------
  6  2  1  .  .  .  9
  .  .  3  .  4 16  .
  .  .  5  8  . 12  .
  7  .  .  .  .  .  .
  .  .  .  .  .  . 10
15 13 11  .  .  .  .
  .  .  .  .  .  . 14
----------------------
and
-------------------------
  1  2  .  .  .  .  5  .
  .  .  3  .  4  .  . 18
  9  7  .  .  6  .  . 16
  .  .  .  .  .  .  . 14
  .  .  .  .  .  .  . 12
  .  .  8  .  .  .  .  .
10 17 15 13  .  .  .  .
  .  .  .  . 11  .  .  .
-------------------------

I've also computed a similar sequence where the line is
allowed to touch itself in single points, but not to cross itself, nor 
to overlap on a segment. I got:
0, 2, 4, 7, 10, 13, 16, 20.

A solution for the case a(8)=20 is
-------------------------
  1  2  .  .  .  .  . 16
  .  .  3  .  .  .  . 14
  9  . 15  .  5  .  . 12
  .  .  4  .  .  .  .  .
  .  .  6 13  .  7  . 21
  .  .  8  . 11  .  . 19
10  .  .  .  .  .  . 17
20 18  .  .  .  .  .  .
-------------------------

I've tentatively created two co-authored sequences
A226595 and A226596. Could you add the link to youtube and improve
the English ?

my program is not very optimized. Probably I can also compute a(9).

Thanks,
Giovanni