|
|
A318165
|
|
The n^n dots problem: minimal number of straight lines (connected at their endpoints) required to pass through n^n dots arranged in an n X n X ... X n grid.
|
|
3
|
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
A generalization of the well-known "Nine Dots Problem".
For any n > 3, an upper bound for this problem is given by U(n) := (t + 1)*n^(n - 3) - 1, where "t" is the best known solution for the corresponding n X n X n case, and (for any n > 5) t = floor((3/2)*n^2) - floor((n - 1)/4) + floor((n + 1)/4) - floor((n - 2)/4) + floor(n/2) + n - 2 (e.g., U(4) = 95, since 23 is the current upper bound for the 4 X 4 X 4 problem). In particular, it is easily possible to prove the existence of an Hamiltonian path without self crossing such that U(4) = 95 (in fact, an Hamiltonian path with link-length 23 for the 4 X 4 X 4 problem was explicitly shown in June 2020).
A (trivial) lower bound is given by B(n):= (n^n - 1)/(n - 1). - Marco Ripà, Aug 25 2020
|
|
LINKS
|
|
|
EXAMPLE
|
For n = 3, a(3) = 13. You cannot touch (the centers of) the 3 X 3 X 3 dots using fewer than 13 straight lines, following the "Nine Dots Puzzle" basic rules.
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,more,hard,bref
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|