Shortest path sequence

[David Wilson]

It is not difficult to show that the length of the path will be even.

Let P be a polygonal path from (0, 0) to (n, n) with vertices
having integer coordinates and edges of integer length.

Let (a, b) be an edge of P.  If gcd(a, b) = g > 1, replace (a, b)
with g vectors (a/g, b/g).  Thus, WLOG, gcd(a, b) = 1.

If a and b are both even, we have gcd(a, b) != 1.  If a and b
are both odd, then a^2+b^2 == 2 (mod 4), so that a^2+b^2 is
not a square, and (a, b) is not of integer length.  We conclude
that a and b are of opposite parity, that is a+b == 1 (mod 2).

Let e be the number of edges of P.  Let (p_i, q_i) (0 <= i <= k)
be the vertices of P, and (a_i, b_i) (0 <= i < k) be its edges.
Then

    (p_(i+1), q_(i+1)) = (p_i, q_i) + (a_i, b_i)
    ==> p_(i+1)+q_(i+1) = (p_i+q_i) + (a_i+b_i)
    ==> p_(i+1)+q_(i+1) == (p_i+q_i) + (a_i+b_i) (mod 2)

But by the above argument, a_i+b_i == 1 (mod 2), so

    [1]  p_(i+1)+q_(i+1) == (p_i+q_i) + 1 (mod 2)

Now, if i = 0, (p_i, q_i) = (0, 0) and p_i+q_i == i (mod 2).
Also, if p_i+q_i == i (mod 2), then by [1]

    p_(i+1)+q_(i+1) == (p_i+q_i) + 1 = i+1 (mod 2)

So by induction we conclude p_i+q_i == i (mod 2) for all i.

Now (p_k, q_k) = (n, n), so p_k+q_k == k (mod 2) implies

    k == p_k+q_k == n+n == 2n == 0 (mod 2).

and k is even, this is P has an even number of edges.

Finally, since for each edge (a, b) of P, a and b are of different
parity, we have a^2+b^2 odd, so that the length of (a, b) =
sqrt(a^2+b^2) is odd.  Whereas P is composed of an even
number of odd-length edges, its total length is even, QED.

The length of P must exceed sqrt(2)*n, the straight line
distance from (0, 0) to (n, n).  The length of P is an even
integer, and the smallest even integer >= sqrt(2)*n is
2*ceil(n/sqrt(2)). which is a lower bound on the length
of P.

I did the greedy algorithm with the edges (0, 1), (3, 4), (20, 21),
etc, for 0 <= n <= 10000, and in each case the length of P
was precisely 2*ceil(n/sqrt(2)).