A225227 - OEIS

%I #119 Aug 05 2023 13:04:39

%S 1,7,13

%N The n X n X n dots problem: minimal number of straight lines (connected at their endpoints) required to pass through n^3 dots arranged in an n X n X n grid, without exiting from the box [0, n] X [0, n] X [0, n].

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

%C From _Marco Ripà_, Aug 10 2020: (Start)

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

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

%H Marco Ripà, <a href="http://dx.doi.org/10.13140/RG.2.2.12199.57769/1">Solving the n_1 <= n_2 <= n_3 Points Problem for n_3 < 6</a>, ResearchGate, 2020.

%H Marco Ripà, <a href="https://doi.org/10.14710/jfma.v3i2.8551">Solving the 106 years old 3^k points problem with the clockwise-algorithm</a>, Journal of Fundamental Mathematics and Applications, 2020, 3(2), 84-97.

%H Marco Ripà, <a href="https://doi.org/10.14710/jfma.v4i2.12053">General uncrossing covering paths inside the Axis-Aligned Bounding Box</a>, Journal of Fundamental Mathematics and Applications, 2021, 4(2), 154-166.

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Thinking_outside_the_box#Nine_dots_puzzle">Nine dots puzzle</a>

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

%Y Cf. A058992, A261547, A318165, A363755.

%K nonn,more,hard,bref

%O 1,2

%A _Marco Ripà_, May 02 2013

%E Entry revised by _N. J. A. Sloane_, May 02 2013

%E a(3) corrected by _Marco Ripà_, Jul 19 2020