A225227 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].

1, 7, 13

Offset: 1

Author

Marco Ripà, May 02 2013

Keywords

• nonn
• more
• hard
• bref

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)

Examples

			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.
		

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

Crossrefs

Cf. A058992, A261547, A318165, A363755.

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

Extensions

Entry revised by N. J. A. Sloane, May 02 2013

a(3) corrected by Marco Ripà, Jul 19 2020