A359740 - OEIS

%I #39 Jan 31 2024 04:00:19

%S 0,-1,-1,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,

%T 26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,

%U 49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67

%N Maximal number of moves needed by a knight to reach every cell from a fixed position on an n X n X n chessboard, or -1 if it is not possible to reach every square.

%C 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).

%C 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).

%C 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.

%C From _Pontus von Brömssen_, Jan 13 2023: (Start)

%C 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)

%C From _Michael S. Branicky_, Jan 21 2023: (Start)

%C 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.

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

%H Michael S. Branicky, <a href="/A359740/a359740.py.txt">Python program computing graph diameter explicitly</a>

%H David Hartenstine, <a href="https://www.math.utah.edu/mathcircle/notes/distance.pdf">Distance and Metric Spaces</a>

%H MathOverflow, <a href="https://mathoverflow.net/questions/437443/chess-pieces-metrics-in-higher-dimensions">MathStackExchange discussion concerning chess pieces metrics on k-dimensional boards</a>

%H Marco Ripà, <a href="https://arxiv.org/abs/2311.00016">Metric spaces in chess and international chess pieces graph diameters</a>, arXiv:2311.00016 [math.HO], 2023. See pp. 11, 14.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/GraphDiameter.html">Graph Diameter</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/KnightGraph.html">Knight Graph</a>

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

%e 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.

%t Join[{0, -1, -1}, Range[4, 100]] (* _Paolo Xausa_, Jan 31 2024 *)

%Y Cf. A232007.

%K sign,easy

%O 1,4

%A _Marco Ripà_, Jan 12 2023

%E a(7)-a(38) using linked program, a(39) and beyond using formula from _Michael S. Branicky_, Jan 21 2023