Re: [math-fun] sketched proof of Knight distance formula
A lower bound on shortest path count of the form polynomial(d) * central binomial coeff may be proved not only for the along-diagonal shortest N-paths at (3k+1, 3k+1), but also for the along axis cases at (4k-1,0). My technique is, essentially, you use the usual minimal path to reach (3k,3k) and (4k,0) plus add one "zig" and one "zag" -- plus in the (4k-1,0) case remove an edge -- so it now reaches (3k+1,3k+1) and (4k-1,0) and still is shortest. The number of ways to insert the zig and the zag, grows quadratically in both the (4k-1,0) and (3k+1,3k+1) cases. In the (4k-1,0) case we also get to remove one edge, which can be done in a linear number of ways. As a result, the shortest path count in this along-axis case indeed wins asymptotically, overwhelming the diagonal case and refuting my flaky conjecture: It grows like a CUBIC times central binomial coefficient, whereas the along-diagonal growth was only QUADRATIC times c.b.c. One should be able to work out exact formulas, or at least more precise lower bounds, for these maximal counts.
I've kind of lost track of this thread. What exactly is the "Knight distance formula" to be proved?
-----Original Message----- From: math-fun- bounces+davidwwilson=comcast.net@mailman.xmission.com [mailto:math- fun-bounces+davidwwilson=comcast.net@mailman.xmission.com] On Behalf Of Warren D Smith Sent: Saturday, April 12, 2014 12:01 AM To: math-fun Subject: Re: [math-fun] sketched proof of Knight distance formula
A lower bound on shortest path count of the form polynomial(d) * central binomial coeff may be proved not only for the along-diagonal shortest N-paths at (3k+1, 3k+1), but also for the along axis cases at (4k-1,0).
My technique is, essentially, you use the usual minimal path to reach (3k,3k) and (4k,0) plus add one "zig" and one "zag" -- plus in the (4k-1,0) case remove an edge - - so it now reaches (3k+1,3k+1) and (4k-1,0) and still is shortest. The number of ways to insert the zig and the zag, grows quadratically in both the (4k-1,0) and (3k+1,3k+1) cases. In the (4k-1,0) case we also get to remove one edge, which can be done in a linear number of ways. As a result, the shortest path count in this along-axis case indeed wins asymptotically, overwhelming the diagonal case and refuting my flaky conjecture: It grows like a CUBIC times central binomial coefficient, whereas the along-diagonal growth was only QUADRATIC times c.b.c.
One should be able to work out exact formulas, or at least more precise lower bounds, for these maximal counts.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Let f(K,L) := the smallest number of knight moves {(+-2,+-1),(+-1,+-2)} it takes to get from square (0,0) to square (K,L) on an infinite chessboard. WLOG assume K,L > 0. Then find an explicit way to express f(K,L), and prove its correctness. --Dan On Apr 12, 2014, at 6:18 AM, David Wilson <davidwwilson@comcast.net> wrote:
I've kind of lost track of this thread. What exactly is the "Knight distance formula" to be proved?
See items 1--5 of https://www.dropbox.com/s/nzmzjswtctju23f/knights_path.txt I'm now satisfied that this proof is correct; however, notification of potential obscurities, typos etc. would still be welcomed. WFL On 4/12/14, Dan Asimov <dasimov@earthlink.net> wrote:
Let f(K,L) := the smallest number of knight moves {(+-2,+-1),(+-1,+-2)} it takes to get from square (0,0) to square (K,L) on an infinite chessboard.
WLOG assume K,L > 0.
Then find an explicit way to express f(K,L), and prove its correctness.
--Dan
On Apr 12, 2014, at 6:18 AM, David Wilson <davidwwilson@comcast.net> wrote:
I've kind of lost track of this thread. What exactly is the "Knight distance formula" to be proved?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
A formula for f(K,L) (and proof thereof) is given in this paper: (I have a copy if anyone is interested. --Edwin) Pattern Recognition Letters 7 (1988) 215 226 April [988 North-Holland Knight's distance in digital geometry P.P. DAS and B.N. CHATTERJI Using the knight's moves in the game of chess, the knight's distance is defined for the digital plane. The functional form is presented. An algorithm is given for tracing a minimal knight's path. The properties of some related topological entities are given. Finally the Knight's transform is defined On Sat, Apr 12, 2014 at 9:54 AM, Dan Asimov <dasimov@earthlink.net> wrote:
Let f(K,L) := the smallest number of knight moves {(+-2,+-1),(+-1,+-2)} it takes to get from square (0,0) to square (K,L) on an infinite chessboard.
WLOG assume K,L > 0.
Then find an explicit way to express f(K,L), and prove its correctness.
--Dan
On Apr 12, 2014, at 6:18 AM, David Wilson <davidwwilson@comcast.net> wrote:
I've kind of lost track of this thread. What exactly is the "Knight distance formula" to be proved?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Correction: I should not have excluded the case L=0. --Dan On Apr 12, 2014, at 11:33 AM, W. Edwin Clark <wclark@mail.usf.edu> wrote:
Let f(K,L) := the smallest number of knight moves {(+-2,+-1),(+-1,+-2)} it takes to get from square (0,0) to square (K,L) on an infinite chessboard.
WLOG assume K,L > 0.
participants (5)
-
Dan Asimov -
David Wilson -
Fred Lunnon -
W. Edwin Clark -
Warren D Smith