OFFSET
1,2
COMMENTS
A generalization of the well-known "Nine Dots Problem", where the regular axis-aligned bounding box (RAABB:=[0, n] X [0, n] X [0, n]) has been declared.
From Marco Ripà, Aug 10 2020: (Start)
In particular, if we loosen the constraint on the allowed AABB, covering paths characterized by a shorter link-length can be found, such as 5 <= a(2) <= 6, where the aforementioned upper bound has been discovered by Koki Goma in August 2021, providing the self-crossing covering path (0,0,0)-(2,2,0)-(1/2,1/2,3/2)-(2,-1,0)-(0,1,0)-(0,1,1)-(0,0,1).
Moreover, the above pattern suggests different uncrossing covering paths of the same link-length, such as (1,0,0)-(0,0,0)-(2,2,2)-(1/2,-1,1/2)-(-1/2,1,3/2)-(1,1,0)-(1,1,0) and also the (self-crossing) covering path (1,0,0)-(0,0,0)-(0,1,0)-(3/2,1,3/2)-(1/2,-1,1/2)-(-1/2,1,3/2)-(1,1,0) which is entirely contained inside a box of 1.5 X 2 X 2 units^3 but which does not match the RAABB. (End)
LINKS
Marco Ripà, Solving the n_1 <= n_2 <= n_3 Points Problem for n_3 < 6, ResearchGate, 2020.
Marco Ripà, Solving the 106 years old 3^k points problem with the clockwise-algorithm, Journal of Fundamental Mathematics and Applications, 2020, 3(2), 84-97.
Marco Ripà, General uncrossing covering paths inside the Axis-Aligned Bounding Box, Journal of Fundamental Mathematics and Applications, 2021, 4(2), 154-166.
Marco Ripà, General conjecture on the optimal covering trails in a k-dimensional cubic lattice, hal-03841209v3, 2023.
Wikipedia, Nine dots puzzle
FORMULA
For any n >= 3, (n^3 - 1)/n - 1) <= a(n) <= floor((3*n^2)/2) - floor((n - 1)/4) + floor((n + 1)/4) - floor((n + 2)/4) + floor(n/4) + n - 2. - Marco Ripà, Oct 25 2024
EXAMPLE
For n = 2, a(2) = 7. You cannot touch the 8 vertices of a cube using fewer than 7 straight lines and without exiting from the box [0, 2] X [0, 2] X [0, 2], following the "Nine Dots Puzzle" basic rules.
CROSSREFS
KEYWORD
nonn,more,hard,bref,changed
AUTHOR
Marco Ripà, May 02 2013
EXTENSIONS
Entry revised by N. J. A. Sloane, May 02 2013
a(3) corrected by Marco Ripà, Jul 19 2020
STATUS
approved