Shortest path sequence

[Roland Bacher]

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