OFFSET
1,2
COMMENTS
a(n) arises from optimal play of the following two-player game, named "The Snake and the Hunter" (see Links), on an n X n grid graph (vertices are grid points, edges connect vertically/horizontally adjacent points).
The description of this game was given in a MathOverflow thread in 2016, and the rules are as follows: Player A starts by selecting any edge between two adjacent vertices; this creates a path. Players A and B then alternate moves. At each move, the current player extends the path by adding one edge at either endpoint, to a previously unused vertex; the path must remain simple: no vertex may be visited more than once (equivalently, no cycles are allowed). The game ends when no further extension is possible, and the score is given by the total number of edges in the resulting path. Player A (the snake) aims to maximize the final length, while player B (the hunter) aims to minimize it.
a(n) is the resulting path length when both players play optimally on an n X n grid. This corresponds to a single round of "The Snake and the Hunter", where player B has the same legal moves but plays to minimize the length.
Values of a(n) for n <= 6 were found by Peter Taylor; see the comments of the MathOverflow thread in Links.
LINKS
Math Overflow, A Combinatorial Game: the Snake and the Hunter.
Peter Taylor, Snake and Hunter.
EXAMPLE
For n = 3, a(n) = 8 since optimal play yields a path of length 3^2 - 1 (and n^2 - 1 is a trivial upper bound for this sequence).
CROSSREFS
KEYWORD
nonn,hard,more
AUTHOR
Marco Ripà, Mar 23 2026
STATUS
approved