Most of WDS's post is subsumed in Theorem 16 of the current screed. Intuitively, local maxima of e(x, y) --- the number of shortest paths to [x, y] --- can be expected to occur along diagonal [3 k + 1, 3 k + 1] at distance 2 k + 2 , or along axis [4 k - 1, 0] at distance 2 k + 1 ; since at those points the Euclidean radius has locally minimal length within (perforated) annulus d(x, y) = constant. Considering maxima over square regions max(|x|, |y|) <= m , diagonal wins; but it seems more natural to consider instead maxima over (almost convex) discs d(x, y) <= d , when axis wins. Including intermediate points to complete the paths, these diagonal and axis sequences as functions of d commence [ 0, 1, 2, 9, 32, 85, 240, 588, 1512, 3564, 8700, 19965, 47124 ]; [ 0, 1, 2, 6, 28, 100, 330, 1050, 3024, 8736, 23220, 62700, 158004 ]; respectively. Fred Lunnon On 4/11/14, Warren D Smith <warren.wds@gmail.com> wrote:
As I remarked to Lunnon in email, I still do not accept that he has proved the N-distance formula. Despite him seeming to think he has. But anyhow, I believe the "brute force proof" I sketched does work.
Another comment is that, apparently, the shortest path from (0,0) to (x,y) is unique if and only if (x,y) is an integer multiple of (+-1,+-2) or (+-2, +-1). Otherwise, at least 2 paths exist, and if KnightDist>2 then at least 3 exist. Indeed the number of shortest paths (whenever non-unique) appears to be lower bounded by some linearly-growing function of the distance, and this seems tight because NumberOfShortestPaths( 2 + 2*k, k-1 ) = k+1 = KnightDist(2+2*k, k-1) for each k>=0. On the other hand, exponential growth is possible as demonstrated by NumberOfShortestPaths( 3*n, 3*n ) = (2*n)!/(n!)^2 for each n>=0 as one can prove by explicit construction of all paths. Here KnightDist(3*n, 3*n) = 2*n. This grows exponentially with ultimate growth ratio 2 as a function of distance d. It naively appears as though NumberOfShortestPaths( 3*n+1, 3*n+1 ) grows faster, but you can easily prove it ultimately also grows exponentially also with growth factor (in the limit) 2. It is however lower bounded by (2*n+2)*(2*n+1)*(2*n)!/(n!)^2 as I can show by explicit construction of that many paths. Here KnightDist(3*n+1, 3*n+1) = 2*n+2. I conjecture (without great confidence) that this formula is the maximum possible to within a constant factor.
If you do not want to take some path, then the next-higher-distance is always 2 greater because of parity. In consequence the "NonUniqueKnightDistance" function, giving the shortest distance in knight moves if your first-choice path is rejected, is equal to the usual KnightDist function, except when (x,y) is an integer multiple of (+-1,+-2) or (+-2, +-1), in which cases add 2 hops.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun