A226595 -id:A226595 - cp's OEIS frontend

A226596 Lengths of maximal non-crossing and non-overlapping increasing paths in n X n grids.

0, 2, 4, 7, 10, 13, 16, 20, 22

Offset: 1

Charles R Greathouse IV and Giovanni Resta, Jun 13 2013

The path is allowed to touch but not cross itself on single points, but not on segments of any length. "Increasing" means that the (Euclidean) length of each line segment must be strictly longer than the last.

			A solution for the case a(8)=20 is
-------------------------
01 02  .  .  .  .  . 16
..  . 03  .  .  .  . 14
09  . 15  . 05  .  . 12
..  . 04  .  .  .  .  .
..  . 06 13  . 07  . 21
..  . 08  . 11  .  . 19
10  .  .  .  .  .  . 17
20 18  .  .  .  .  .  .
-------------------------

Giovanni Resta, Illustration of a(2)-a(9)
Gordon Hamilton, $1,000,000 Unsolved Problem for Grade 8 (2011)

Cf. A226595.

a(n) <= A160663(n-1).

A253620 Maximum number of segments in nonintersecting increasing path on n X n hexagonal (isogonal) grid.

Original entry on oeis.org

0, 3, 6, 10, 14, 19, 25, 30, 36

Offset: 1

Tim Cieplowski, Jan 06 2015

The path cannot intersect itself, not even on single points. "Increasing" means that the (Euclidean) length of each segment must be strictly greater than that of the previous one.

The analogous sequence for a triangular (isogonal) grid seems to satisfy a(n) = 2n+1, with 2^(n-2) such paths up to isomorphism.

			An example for a(4) = 10
       .   .   .   .
    09   .   .   .   .
  01   .   .   .   .   .
00  07   .   .   .   .  10
  02  05   .   .   .  08
     .   .   .   .  06
      03   .   .  04

Tim Cieplowski, Illustration of first few terms
Gordon Hamilton, $1,000,000 Unsolved Problem for Grade 8 (2011)

Cf. A226595.

A272719 Maximal number of steps in a nontouching path on an n X n grid such that each step has a different length.

Original entry on oeis.org

2, 5, 8, 12, 17

Offset: 2

Giovanni Resta, May 05 2016

a(7) >= 22, see illustration in Links.

			An example for a(6)=17:
----------------
.  2  5  7  9 15
3  1  .  . 11 17
.  .  .  .  .  .
.  6  . 12  .  .
4 10  .  .  .  .
8 13  . 14 16 18

Giovanni Resta, Illustration of a(2)-a(6) and a(7) >= 22

Cf. A226595.

A358212 a(n) is the maximal possible sum of squares of the side lengths of an n^2-gon supported on a subset 1 <= x,y <= n of an integer lattice.

Original entry on oeis.org

4, 10, 36, 98, 232

Offset: 2

Giedrius Alkauskas, Nov 04 2022

Examples show that a(7) >= 462, a(8) >= 842, a(9) >= 1424, a(10) >= 2242.

Asymptotics: liminf a(n)/n^4 >= 8/27, limsup a(n)/n^4 <= 2/3.

Oliver Mantas Ališauskas, Grid connector, Web application for this problem.
Oliver Mantas Ališauskas, Giedrius Alkauskas, and Valdas Dičiūnas, Full Grid Lattice Polygons with Maximal Sum of Squares of Edge-Lengths, arXiv:2311.03011 [math.CO], 2023-2024.
S. Chow, A. Gafni, and P. Gafni, Connecting the dots: maximal polygons on a square grid, Math. Mag. 94 (2021), no. 2, 118-124.
G. L. Cohen and E. Tonkes, Dartboard arrangements, Elect. J. Combin., 8(2) (2001), #R4.

Cf. A209077, A110611, A064842, A226595, A226596.

a(5) from Giedrius Alkauskas, Oct 09 2023

a(6) from Giedrius Alkauskas, Nov 30 2023

cp's OEIS Frontend

A226596 Lengths of maximal non-crossing and non-overlapping increasing paths in n X n grids.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A253620 Maximum number of segments in nonintersecting increasing path on n X n hexagonal (isogonal) grid.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A272719 Maximal number of steps in a nontouching path on an n X n grid such that each step has a different length.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A358212 a(n) is the maximal possible sum of squares of the side lengths of an n^2-gon supported on a subset 1 <= x,y <= n of an integer lattice.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions