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