|
%I #14 Jul 22 2024 15:36:43
%S 0,3,12,20,28,40,53,68,85,104,125,148,173,200,229,260,293,328,365,404,
%T 445,488,533,580,629,680,733,788,845,904,965,1028,1093,1160,1229,1300,
%U 1373,1448,1525,1604,1685,1768,1853,1940,2029,2120,2213,2308,2405,2504
%N Integer part of the total Euclidean length of the shortest minimum-link polygonal chains joining all the nodes of the grid {0,1,...,n-1} X {0,1,...,n-1}.
%C 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.
%C 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.
%C 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.
%C (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).
%H Marco Ripà, <a href="https://arxiv.org/abs/2207.08708">Shortest polygonal chains covering each planar square grid</a>, arXiv:2207.08708 [math.CO], 2022. See pp. 11-13.
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (3,-3,1).
%F 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.
%F For n > 5, a(n) = n^2 + 4.
%F 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
%e 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.
%t Join[{0, 3, 12, 20, 28} Table[Floor[n^2 + 5*Sqrt[2]] - 3 , {n, 6, 50}]]
%Y Cf. A002193, A010000, A058992, A373537.
%K nonn,easy
%O 1,2
%A _Marco Ripà_, Jun 30 2024
|
