|
%I #27 May 04 2022 00:31:41
%S 0,1,2,5,6,9,12,17,20,27,30,39,42,51,56,67,72,85,90,105,110,125,132,
%T 149,156,175,182,203,210,231,240,263,272,297,306,333,342,369,380,409,
%U 420,451,462,495,506,539,552,587,600,637,650,689,702,741,756,797,812
%N Length of the longest self avoiding walk through a grid such that either x or y is changed by +1 or -1 in each step, and with 0 <= y, 0 <= x <= y, x + y <= n starting at (0,0) and terminating at (x,y) = (n,0).
%C The number of reachable nodes in the grid is given by A002620(n+2).
%C This sequence is inspired by the "Cinnamon Stars" problem given in the link. In this sequence an additional restriction that the walk must terminate at (n,0) has been added.
%H Die Mathe-Adventskalender, <a href="https://www.mathekalender.de/wp/calendar/challenges/challenge-03/">Cinnamon Stars</a>
%H <a href="/index/Rec#order_11">Index entries for linear recurrences with constant coefficients</a>, signature (1,1,-1,0,0,0,0,1,-1,-1,1).
%F a(n) < A002620(n+2).
%F From _Andrew Howroyd_, Dec 18 2021: (Start)
%F a(2*n) = n*(n + 1); a(2*n-1) = n^2 + n - 1 - 2*floor((n+1)/4).
%F G.f.: x*(1 + x + 2*x^2 + 2*x^5 + 2*x^6 + x^8 - x^9)/((1 - x)^3*(1 + x)^2*(1 + x^2)*(1 + x^4)).
%F a(n) = a(n-1) + a(n-2) - a(n-3) + a(n-8) - a(n-9) - a(n-10) + a(n-11) for n >= 11. (End)
%e a(5) = 9. An optimal path is illustrated below:
%e o---o
%e | |
%e o---o o o
%e | |
%e o---o o o---o---o
%e .
%e For n<13, an optimal path can be constructed by moving in y direction as far as possible (also avoiding dead ends), then moving one step in positive x direction, and going back in the other y direction. For example, a(6) = 12:
%e o
%e .
%e o o---o
%e | |
%e o---o o o o
%e | | | |
%e o---o o---o o---o---o
%e .
%e From _Andrew Howroyd_, Dec 18 2021: (Start)
%e For even n, if vertices are colored alternately black and white there will be (n+2)*(n+4)/8 black vertices and n*(n+2)/8 white vertices. Since the walk must alternate between the two colors, the maximum length of the walk is limited to n*(n+2)/4. An optimal construction for a(10) is shown below. Many other solutions exist, but they all have the property that every white vertex is visited.
%e x
%e .
%e x o---x
%e | |
%e x---o x o x
%e | | | |
%e x o x o x o---x
%e | | | | | |
%e x---o x o x o x o x
%e | | | | | | | |
%e x---o x---o x---o x---o x---o---x
%e .
%e For odd n, there will be an equal number of both colors. However, there is an imbalance between left and right halves that must be mitigated. The optimal solution is to fill in along the dividing line as shown below for a(11) = 39. In the illustration, black vertices are marked with x and white with o. Notice that the connections across the dividing line are always between a black vertex on the left and a white on the right. Even with the central crossings placed there will be more black vertices than white on the left (and vice versa on the right). An optimal solution is one in which every white vertex on the left side and every black vertex on the right side is included in the walk.
%e x---o
%e | |
%e x---o x---o
%e | |
%e x---o x---o x---o
%e | | | |
%e x o x---o x---o---x o
%e | |
%e x---o x o x---o x---o x---o
%e | | | | | | | | | |
%e x---o x---o x---o x---o x---o x---o
%e (End)
%o (PARI) a(n)=if(n%2, (n^2 + 4*n - 1)/4 - (n+3)\8*2, n*(n/2 + 1)/2) \\ _Andrew Howroyd_, Dec 18 2021
%Y Cf. A002620.
%K easy,nonn,walk
%O 0,3
%A _Paul Bischof_, Dec 04 2021
%E Terms a(17) and beyond from _Andrew Howroyd_, Dec 18 2021
|
