Shortest path sequence

[David C Terr]

I like your solution. In fact, I just thought of it myself! Note that your 
solution consists of a series of flattened staircases, with the most 
flattened one
starting at (0,0) and becoming less flat approaching (n,n). I wonder what 
the solution is for a hexagonal lattice.

Dave






Roland Bacher <Roland.Bacher at ujf-grenoble.fr>
03/23/2005 10:30 PM

 
        To:     David Wilson <davidwwilson at comcast.net>
        cc:     Sequence Fans <seqfan at ext.jussieu.fr>
        Subject:        Re: Shortest path sequence

On Wed, Mar 23, 2005 at 12:59:25PM -0500, David Wilson wrote:
> Let a(n) be the length of the shortest path from (0, 0) to (n, n)
> whose steps are of integer length and start and end on integer
> coordinates.
> 
> For example, we can always go from (0, 0) to (n, n) in two
> steps, from (0, 0) to (0, n) to (n, n), so a(n) <= 2n.  Since
> the path must be at least as long as the straight-line path from
> (0, 0) to (n, n), we have a(n) < sqrt(2) n.  It is not hard to
> construct examples with a(n) arbitrarily close to sqrt(2) n, and
> I am sure that lim n->inf a(n)/n = sqrt(2).
> 
> So can we compute a(n) efficiently?
> 
> 
> 
> - David W. Wilson
> 
> "Truth is just truth -- You can't have opinions about the truth."
>   - Peter Schickele, from P.D.Q. Bach's oratorio "The Seasonings"


By your comment you want steps containing no integral intermediate
points

A stupid answer is $n\sqrt{2}$ since you can  take $n$ steps $(1,1)$.

I guess you don't like this one. The correct answer is then
something like

$\sqrt{\lfloor (n-1)/2\rfloor^2+\lfloor (n+1)/2\rfloor^2}+
\sqrt{(n-\lfloor (n-1)/2\rfloor)^2+(n-\lfloor (n+1)/2\rfloor)^2}$

(geometrically, go in two steps from (0,0) to (n,n) by making
a stop at (one of the four) integral points which are closest
and different from (n/2,n/2) )
This is obviously the shortest such path which is not straight.

 
Best whishes,   Roland Bacher


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.seqfan.eu/pipermail/seqfan/attachments/20050324/c6b235f4/attachment-0001.htm>