<< Denote e(x, y) the number of shortest knight paths from (0,0) to (x,y) . Prove that e(1999999999, 3) = e(1500000000, 1499999998) . >> A week ago I half-promised a solution for this question; so below follows a sketch glossing over the more gruesome details. The infinite chess-board lattice |Z^2 centred at the origin is subdivided into 8 sectors of alternating types: "A-regions" clustering about axes y = 0 & x >= 0 etc, and "B-regions" clustering about diagonals y = x & x,y >= 0 etc. The sectors are approximately separated by boundary lines along dilated knight moves x = 2y etc, though not exclusively: adjacent sectors intersect in common "C-region" bands spanning 4 lattice points wide. e(P) counts shortest knight paths from O = (0, 0) to P = (x, y) , of length in knight steps d(P) . By symmetry, we can assume x >= y >= 0 for the P under discussion (this may not necessarily hold for its neighbours). We also assume that d > 4 in order to avoid special cases near O , smaller cases being resolved by inspection. Then the distance formula simplifies to d(P) = x-y - 2t with t = [(x - 2y)/4] for P in A-region; x-y + 2t with t = [(2y - x)/3] for P in B-region. Note that e(P) equals the sum of e(P') , where P' ranges over "nearer" neighbours having d(P') = d(P) - 1 . As a first step, consider "type 0" paths, stretched as tautly as possible in some given direction: type A0 where P = (2d, d - 2t) ; type B0 where P = (2d - t, d + t) . Via the distance formula, such P can be shown to have (usually) 2 nearer neighbours: for type A0 , P' = (x-2, y+1), (x-2, y-1) ; for type B0 , P' = (x-1, y-2), (x-2, y-1) ; both P' are also of type A0 and B0 respectively. With a suitable change of coordinates, either set of e(P) becomes a Pascal triangle, so the answer is simply a binomial coefficient: for type 0 , ### e(2d, d - 2t) = e(2d - t, d + t) = d_C_t . ### Moving on, "type 1" paths have more wiggle room: type A1 where P = (2d - 1, d - 1 - 2t) ; type B1 where P = (2d - 1 - t, d - 1 + t) . Now there are (usually) 2+2 nearer neighbours: for type A1 , P' = (x-1, y+2), (x-1, y-2), (x-2, y+1), (x-2, y-1) ; for type B1 , P' = (x+1, y-2), (x-2, y-1), (x-1, y-2), (x-2, y-1) ; their types are A0,A1 and B0,B1 respectively. This yields a recurrence for e(P) in terms of nearer values and binomial coefficients. An appropriate ansatz (phwoar!) and some graft with difference tables on precomputed values delivers ### e(P) = ( d^2 - (2t+1)d + 2t(t+1) ) * (d+1)_C_(t+1) / (d+1) for type A1 ; e(P) = ( d^3 - 3t d^2 + (3t^2 - 1)d ) * (d+2)_C_(t+1) / (d+1)(d+2) for type B1 . ### These can then be verified via tedious induction; potentially hideous complications as t approaches its end-points near 0,d can be averted utilising the common C-region. We could continue on now, to types A2, B2, A3. Fortunately there's no need, because the question requires the special cases of A1 and B1 when d is even and t = d/2 - 1 . For such arguments there occurs this striking coincidence: after simplification and re-arrangement, ### e(2d-1, 3) = e((3/2)d, (3/2)d-2) = 2 d_C_(d/2 - 1) + d d_C_(d/2 - 2) . ### QED. The values for distance d = 0(2)12 are e = 2, 2, 12, 66, 336, 1620; for d = 10^9 , e has around 3.10^8 decimal digits. If you have managed to struggle through to here, maybe now you understand why I'd like to see a more straightforward solution! Fred Lunnon On 5/30/14, Gareth McCaughan <gareth.mccaughan@pobox.com> wrote:
One possible way to approach these things that maybe has more of the "intrinsic" feel Fred is looking for:
Let F : Z^4 -> Z^2 map the four standard basis vectors to four "basis" vectors of the knight's-move lattice; so it's represented by, say, the matrix (1 1 2 2; 2 -2 1 -1).
The preimages of any point in Z^2 form a 2-dimensional lattice within Z^4 (offset by some single preimage) whose basis vectors are, if I've not messed up the routine calculations to get them, (1;-1;-2;2) and (-2;-2;1;1).
Now questions about distances and shortest paths for a knight on the chessboard become questions about distances and shortest paths from the origin to *any point of that lattice* in Z^4. Or, equivalently, consider only the preimage lattice of 0 and ask about distances from some single preimage to *any point of that lattice*.
So, for instance, the question about (2n,n) is the same as: show that of all points (a-2b;-a-2b;n-2a+b;2a+b), the one with the smallest L1-norm is (0;0;n;0).
It's not obvious to me that this actually makes anything easier, but I think there's a fair chance that there's some single further bit of technique that makes all these questions, viewed from this perspective, routine.