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,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

Table of n, a(n) for n=1..3.

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.

Wikipedia, Nine dots puzzle

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

Cf. A058992, A261547, A318165, A363755.

Sequence in context: A219777 A157808 A354301 * A217793 A299472 A285642

Adjacent sequences: A225224 A225225 A225226 * A225228 A225229 A225230

Keyword

nonn,more,hard,bref

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