|
%I #81 Mar 01 2023 14:51:01
%S 0,2,1,3,3,4,4,4,5,7,4,5,6,7,9,5,5,6,8,10,12,5,6,7,8,10,12,14,6,6,7,9,
%T 10,12,14,17,6,7,8,9,11,13,15,17,19,6,7,8,9,11,13,15,17,19,21,7,7,8,
%U 10,11,13,15,17,19,22,24,7,8,9,10,12,13,15,17,20,22,24,26
%N Table T(i,j), i >= 0, j >= 0, read by antidiagonals giving the smallest number of moves needed to win Integer Lunar Lander, starting from position (i,j). Game rules in comments.
%C A position in the game of Integer Lunar Lander consists of an ordered pair (i,j) of integers. There are always 3 legal moves, to (i+1,j+i+1), (i,j+i), and (i-1,j+i-1). The object of the game is to reach (0,0) in the minimum possible number of moves, T(i,j). The listed data was provided by _Tom Karzes_.
%C The ordered pair may be interpreted as the upward velocity and altitude of a vehicle; the object is to land the vehicle at zero velocity. In this version negative altitudes are permitted (that is, there is no crash detection, and the optimal trajectory is allowed to go underground without ill effects).
%C Are any of the numbers different if crashes are forbidden? It seems not, slowing to a soft landing always seems to produce a better solution than overshooting the surface and climbing back up. Of course from some initial positions like (-5,1) it is impossible not to crash. But it appears that if a soft landing is possible, then the optimal solution doesn't crash.
%C The game was invented in the early 1970's as a trivial version of a two-dimensional pencil-and-paper game that has been played at least since the first half of the 20th century.
%C Solution lengths for the corresponding game on triples would be interesting for (0,0,n) or (n,0,0).
%C Conjecture 1: For all i, j, T(i,j) differs from its eight neighbors by at most 3. The array of differences {T(i+1,j) - T(i,j)} might be worth studying, as well as the array {T(i,j) mod 2}. - _N. J. A. Sloane_, Feb 25 2023
%C Conjecture 2 (Start)
%C The zeroth row (0,j) is T(0,j) = 1+ floor(sqrt(4j-3)). j>0.
%C Let t_k = k(k+1)/2 be a triangular number.
%C Then the i-th row, {(i,j), j>=0}, is given by
%C T(i,j) = T(0, j+t_{i-1}) + i for i>0.
%C In other words, to get the i-th row, shift the zeroth row to the left by i*(i-1)/2 places and add i to each term.
%C This would imply that the leading column, T(i,0), is equal to i+1+floor(sqrt(2*i^2-2*i-3)) for i >= 2.
%C (End) - _N. J. A. Sloane_, Feb 25 2023
%C Conjecture 1 seems to hold for all (i,j) except (1,0) and (2,1). - _M. F. Hasler_, Feb 27 2023
%D Martin Gardner, "Sim, Chomp, and Race Track", "Mathematical Games", Scientific American, January, 1973. Reprinted in "Knotted Doughnuts and Other Mathematical Entertainments", W. H. Freeman, 1986, pp. 109-122.
%H Rémy Sigrist, <a href="/A360923/b360923.txt">Table of n, a(n) for n = 0..10010</a>
%H Hans Havermann, <a href="http://chesswanks.com/txt/RaceTrack.html">Transcription of Gardner's account of the 2-D game</a>.
%H Rémy Sigrist, <a href="/A360923/a360923.txt">C++ program</a>
%H Rémy Sigrist, <a href="/A360923/a360923.png">Scatterplot of (i, j) at an even number of moves from (0, 0) with abs(i), abs(j) <= 400</a>
%H Rémy Sigrist, <a href="/A360923/a360923_1.png">Scatterplot of (i, j) at up to 400 moves from (0, 0)</a> (the color is function of the number of moves)
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Racetrack_(game)">Racetrack (game)</a> (a 2D version), as of June 2022.
%e For the starting position (2,3), a 6-move solution is (1,4), (0,4), (-1,3), (-2,1), (-1,0), (0,0). No shorter solution is possible, so T(2,3) = 6.
%e The upper left corner of the table i:
%e 0 2 3 4 4 5
%e 1 3 4 5 5
%e 4 5 6 6
%e 7 7 8
%e 9 10
%e 12
%e The first few antidiagonals are
%e 0
%e 2 1
%e 3 3 4
%e 4 4 5 7
%e 4 5 6 7 9
%o (C++) See Links section.
%o (PARI) M360923=Map(); T360923=0; S360923=[[0, 0]]; A360923(v, x)={iferr(mapget( M360923, [v,x]), E, while(!setsearch(S360923, [v,x]), foreach(S360923, vx, vx[1]>=0 && mapput(M360923, vx, T360923)); S360923 = Set(concat([[[u,vx[2]-vx[1]] | u<-[vx[1]-1..vx[1]+1], !mapisdefined(M360923, [u,vx[2]-vx[1]])] | vx <- S360923, vx[2]>=vx[1]])); T360923 += 1); T360923)} \\ _M. F. Hasler_, Feb 27 2023
%o T(i,j)=if(i,T(0,j+i*(i-1)\2)+i,j,sqrtint(4*j-3)+1) \\ Implementing Conjecture 2. - _M. F. Hasler_, Feb 27 2023
%o (Python) # From _M. F. Hasler_, Feb 27 2023: (Start)
%o def A360923(v, x, A={0:0, 1:{(0,0)}}):
%o if (v,x) in A: return A[v,x]
%o while (v,x) not in A[1]:
%o A.update((vx,A[0]) for vx in A[1] if vx[0]>=0); A[0] += 1
%o A[1] = {(u,x-v) for v,x in A[1] if x >= v
%o for u in range(v-1,v+2) if (u,x-v) not in A}
%o return A[0] # (End)
%Y Cf. A360924, A360925, A360926.
%K nonn,tabl,nice
%O 0,2
%A _Allan C. Wechsler_, Feb 25 2023, using information about the original game from _Eric Angelini_, _Hans Havermann_, and _M. F. Hasler_, and data from _Tom Karzes_.
%E More terms from _Rémy Sigrist_, Feb 26 2023
|
