A357234 -id:A357234 - cp's OEIS frontend

A357516 Number of snake-like polyominoes in an n X n square that start at the NW corner and end at the SE corner and have the maximum length.

1, 2, 6, 20, 2, 64, 44, 512, 28, 4, 64, 520, 480, 6720, 43232, 14400

Offset: 1

Yi Yang, Oct 01 2022

The maximum length is given by A357234(n).
If the lower bounds of A357234(n) are tight, then a(14)-a(19) are 6720, 43232, 14400, 226560, 1646080, 403712.
For n > 1, a(n) is even since for every solution there is also the symmetrical solution reflected in the main diagonal.

			For n = 5, there are 2 such snakes shown as follows:
  X . X X X         X X X X X
  X . X . X         . . . . X
  X . X . X         X X X X X
  X . X . X         X . . . .
  X X X . X         X X X X X

Yi Yang, The longest road in a square grid (see 2nd post with a C++ program that generates a(2)-a(19)).

Cf. A331986, A357234.

a(14)-a(16) from Andrew Howroyd, Feb 28 2023

A357359 Maximum number of nodes in an induced path (or chordless path or snake path) in the n X n torus grid graph.

Original entry on oeis.org

5, 8, 14, 21, 28, 39, 50

Offset: 3

Pontus von Brömssen, Sep 25 2022

It is somewhat unclear how a(n) should be defined for n <= 2. If the 1 X 1 and 2 X 2 torus grid graphs are considered to have loops and multiple edges, respectively, we have a(1) = 0 and a(2) = 1 (unless loops and multiple edges are allowed in a path), otherwise a(1) = 1 and a(2) = 3.

			Longest induced paths (with one end in the lower left corner) for 3 <= n <= 7:
  . X X   . X X .   . X X . X   . X X . X .   . . . X . X X
  X X .   X X . .   . X . X X   X X . X X .   X X . X X . X
  X . .   X . X .   X X . X .   X . X X . X   . X X . X X .
          X . X .   X . X X .   . X X . X X   X . X X . X X
                    X . X . .   X X . . X .   X X . X . . .
                                X . X . X .   . X . X . X X
                                              X X . X . X .

Wikipedia, Induced path.

Cf. A331968, A357234, A357358.

a(n) ~ 2*n^2/3.
a(n) <= (2*n^2-1)/3.
a(n) >= A357358(n) - 1.
a(n) >= A331968(n-1).

A375298 Length of the longest winning path in n X n Hex.

Original entry on oeis.org

1, 2, 5, 8, 11, 16, 23, 30, 37, 47, 57, 69, 81, 94, 109, 124, 140, 157, 175, 195, 215, 236, 259, 282, 306, 331, 357, 385, 413, 442, 473, 504, 536, 569, 603, 639, 675, 712, 751, 790, 830, 871, 913, 957, 1001, 1046, 1093, 1140, 1188, 1237, 1287, 1339, 1391, 1444, 1499, 1554, 1610, 1667, 1725, 1785

Offset: 1

Peter Selinger, Aug 12 2024

A winning path is a set of cells connecting the top edge to the bottom edge, minimal with respect to inclusion.

			The longest winning path for 10 X 10 Hex has length 47.
====================
 X . . . . . . . . .
  X X X X X X X X X X
   . . . . . . . . . X
    . X X X . X X X . X
     X . . X X . . X . X
      X X . . . X X . X .
       . X . X X . . . X X
        X . X . . X X . . X
         X . X X X . X X X .
          X . . . . . . . . .
          ====================

Peter Selinger, Table of n, a(n) for n = 1..10000
Peter Selinger, Longest winning paths in Hex, arXiv:2408.05601 [math.CO], 2024.

Number of solutions is A375299.

Cf. A357234.

def a(n):
  if n == 1:
    return 1
  elif n == 2:
    return 2
  elif n == 3:
    return 5
  elif n == 4:
    return 8
  elif n == 9:
    return 37
  elif n % 8 == 3:
    return (2*n**2 - n + 1) // 4 - 1
  else:
    return (2*n**2 - n + 1) // 4

Provably for n >= 10: a(n) = n^2/2 - n/4 - 3/4 if n ≡ 3 (mod 8), and a(n) = floor(n^2/2 - n/4 + 1/4) otherwise.

A357360 Maximum length of an induced path (or chordless path or snake path) between two antipodal nodes of the n-dimensional hypercube.

Original entry on oeis.org

0, 1, 2, 3, 4, 11, 24

Offset: 0

Pontus von Brömssen, Sep 25 2022

The length is defined as the number of edges along the path, so the number of nodes of the longest path is a(n)+1.

			For n <= 4, the only induced paths between two antipodal nodes are the shortest paths, so a(n) = n.
For n = 5, a longest induced path is 00000 - 10000 - 11000 - 11100 - 01100 - 01110 - 00110 - 00111 - 00011 - 10011 - 11011 - 11111, so a(5) = 11.

Cf. A099155 (the ends of the path does not have to be antipodal), A357234 (paths between opposite corners of a square grid).

Main diagonal of A357499.

a(n) <= A099155(n).

cp's OEIS Frontend

A357516 Number of snake-like polyominoes in an n X n square that start at the NW corner and end at the SE corner and have the maximum length.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A357359 Maximum number of nodes in an induced path (or chordless path or snake path) in the n X n torus grid graph.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A375298 Length of the longest winning path in n X n Hex.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Formula

A357360 Maximum length of an induced path (or chordless path or snake path) between two antipodal nodes of the n-dimensional hypercube.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula