Shortest path sequence
David Wilson
davidwwilson at comcast.net
Wed Mar 23 18:59:25 CET 2005
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"
More information about the SeqFan
mailing list