OFFSET

1,4

COMMENTS

The author conjectures that, for any n greater than 3, a(n) = n, while all the 10 independent cases has been manually checked for n = 5 and n = 6 (if n = 4, there are only 4 cases to be checked in order to show that a(4) = 4).

As noted by Eric Weisstein in A232007, a(n) is the graph diameter of the n X n X n knight graph (or -1 if the graph is disconnected).

In general, by assuming n > 3, it is not hard to prove that d(n,k)(N), the knight graph diameter for a k-dimensional n X n X ... X n board, belongs to the closed interval [(ceiling(n*sqrt(k))/sqrt(5), k*n] if n is odd and to [(ceiling(n*sqrt(k))/sqrt(5), k*(n + 1)] if n is even.

From Pontus von Brömssen, Jan 13 2023: (Start)

a(n) >= n can be proved by showing that at least n moves are required to go from a corner cell to a cell adjacent to the diagonally opposite corner: First note that the (Manhattan) distance between those two cells is 3(n-1)-1, and each knight move changes the distance by at most 3, so we need at least n-1 moves. Color each cell black or white according to the parity of the sum of the coordinates. Then each move changes the color of the current cell. The starting cell and the target cell have the same color if n is even and different colors if n is odd. This means that after n-1 moves we are at the wrong color, so we need at least n moves. (End)

From Michael S. Branicky, Jan 21 2023: (Start)

For n > 5, a(n) <= max{a(n-1)+1, a(n-2)+2} since all but the corner in the newly added n-th "shell" has a neighbor in the (n-1)-th shell, and the corner has a neighbor at distance 2 in the (n-2)-th shell.

Combining with the lower bound above, a(n) = n for n > 3 by induction. (End)

LINKS

Michael S. Branicky, Python program computing graph diameter explicitly

David Hartenstine, Distance and Metric Spaces

Marco Ripà, Metric spaces in chess and international chess pieces graph diameters, arXiv:2311.00016 [math.HO], 2023. See pp. 11, 14.

Eric Weisstein's World of Mathematics, Graph Diameter

Eric Weisstein's World of Mathematics, Knight Graph

FORMULA

a(n) = n for n >= 4 (conjectured by author; proved above).

EXAMPLE

a(4) = 4, since we can reach any cell of a n X n X n chessboard, from any given starting position, by spending at most 4 knight moves. For a 3 X 3 X 3 chessboard, it is impossible to reach the middle cell starting from any other, so a(3) = -1.

MATHEMATICA

Join[{0, -1, -1}, Range[4, 100]] (* Paolo Xausa, Jan 31 2024 *)

CROSSREFS

KEYWORD

sign,easy

AUTHOR

Marco Ripà, Jan 12 2023

EXTENSIONS

a(7)-a(38) using linked program, a(39) and beyond using formula from Michael S. Branicky, Jan 21 2023

STATUS

approved