OFFSET
1,2
COMMENTS
This sequence describes the optimal solution of the 2D generalization of the well-known nine dots problem, published in Loyd’s Cyclopedia of Puzzles (1914), p. 301.
Since Solomon Golomb constructively proved that, for any n >= 3, the minimum-link polygonal chain covering a given {0,1,...,n-1} X {0,1,...,n-1} grid consists of (exactly) 2*(n - 1) line segments, we only need to find the shortest trail satisfying the constraint above.
In detail, if n = 2, the trivial spanning path (0,1)-(0,0)-(1,0)-(1,1) is optimal. If n = 3, we have the classic solution of the nine dots problem (0,1)-(0,3)-(3,0)-(0,0)-(2,2). Now, if n > 3, a valid upper bound is given by n^2 + 5*sqrt(2) - 3, but it is possible to improve this solution for the n = 5 case by providing the trail.
(2,3)-(4,3)-(1,0)-(1,3)-(4,0)-(0,0)-(0,4)-(4,4)-(4,1), whose total Euclidean length is 20 + 6*sqrt(2). In the end, assuming n > 5, we can recycle the mentioned solution, then extend the last line segment to reach (4,-1), and finally apply the square spiral pattern to the (extended) ending segment of the {0,1,...,n-1} X {0,1,...,n-1} grid solution in order to get the solution for the {0,1,...,n} X {0,1,...,n} case, joining 2*n + 1 more points by spending two additional line segments having a combined length of 2*n (and this is an iterative strategy which is optimal for any n > 5).
LINKS
Marco Ripà, Shortest polygonal chains covering each planar square grid, arXiv:2207.08708 [math.CO], 2022. See pp. 11-13.
Index entries for linear recurrences with constant coefficients, signature (3,-3,1).
FORMULA
a(1) = 1, a(2) = 3, a(3) = floor(5*(1+sqrt(2))) = 12, a(5) = floor(20 + 6*sqrt(2)) = 28, and a(n) = floor(n^2 + 5*sqrt(2)) - 3 iff n = 4 or n >= 6.
For n > 5, a(n) = n^2 + 4.
G.f.: x^2*(3 + 3*x - 7*x^2 + x^3 + 4*x^4 - 3*x^5 + x^6)/(1 - x)^3. - Stefano Spezia, Jul 02 2024
EXAMPLE
a(2) = 3 since we can join the points {0,1}^2 with a spanning path consisting of 3 line segments having a total Euclidean length of 2^2 - 1.
MATHEMATICA
Join[{0, 3, 12, 20, 28} Table[Floor[n^2 + 5*Sqrt[2]] - 3 , {n, 6, 50}]]
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Marco Ripà, Jun 30 2024
STATUS
approved