Problem E and Solution

The Shortest Path

On the Cartesian plane, we draw grid lines at integer points along the \(x\) and \(y\) axes. We can then draw paths along these grid lines between any two points with integer coordinates. The graph below shows two paths along these grid lines from \(O(0,0)\) to \(P(6,-4)\). One path has length \(10\) and the other has length \(20\).

There are many different paths along the grid lines from \(O\) to \(P\), but the smallest possible length of
such a path is \(10\). Let’s call this
smallest possible length the *path distance* from \(O\) to \(P\).

Determine the number of points with integer coordinates for which the path distance from \(O\) to that point is \(10\).

**Solution 1**

Let \(Q(a,b)\) be a point that has path distance \(10\) from \(O(0,0)\).

Let’s first suppose that \(Q\) lies
on the \(x\) or \(y\) axis.

The only point along the positive \(x\)-axis that has path distance \(10\) from the origin is \((10,0)\).

The only point along the negative \(x\)-axis that has path distance \(10\) from the origin is \((-10,0)\).

The only point along the positive \(y\)-axis that has path distance \(10\) from the origin is \((0,10)\).

The only point along the negative \(y\)-axis that has path distance \(10\) from the origin is \((0,-10)\).

Therefore, there are \(4\) points along
the axes that have a path distance \(10\) from \(O\).

Next, let’s suppose \(a>0\) and
\(b>0\), so \(Q\) is in the first quadrant.

Since the path distance from \(O\) to
\(Q\) is \(10\), there must be a path from \(O\) to \(Q\) that moves a total of \(r\) units to the right and \(u\) units up (in some order) such that
\(r+u = 10\). This means that \(Q\) is \(r\) units to the right of \(O\) and \(u\) units up from \(O\). In other words, \(a=r\) and \(b=u\), so \(a+b =
r+u = 10\).

The points \((a,b)\) in the first quadrant that satisfy \(a+b = 10\) where \(a\) and \(b\) are integers are \((1,9)\), \((2,8)\), \((3,7)\), \((4,6)\), \((5,5)\), \((6,4)\), \((7,3)\), \((8,2)\), \((9,1)\). There are \(9\) such pairs. Therefore, there are \(9\) points in the first quadrant that have path distance \(10\) from \(O\).

By symmetry, there are \(9\) points
in each quadrant that have path distance \(10\) from \(O\).

In quadrant \(2\), the points are \((-1,9)\), \((-2,8)\), \((-3,7)\), \((-4,6)\), \((-5,5)\), \((-6,4)\), \((-7,3)\), \((-8,2)\), \((-9,1)\). In quadrant \(3\), the points are \((-1,-9)\), \((-2,-8)\), \((-3,-7)\), \((-4,-6)\), \((-5,-5)\), \((-6,-4)\), \((-7,-3)\), \((-8,-2)\), \((-9,-1)\). In quadrant \(4\), the points are \((1,-9)\), \((2,-8)\), \((3,-7)\), \((4,-6)\), \((5,-5)\), \((6,-4)\), \((7,-3)\), \((8,-2)\), \((9,-1)\).

Therefore, there are a total of \(4 + (4\times 9) = 40\) points with integer coordinates that have path distance \(10\) from \(O\).

**Solution 2**

We are permitted \(10\) moves to get from the origin to a point by travelling along the grid lines. These moves can be all horizontal (in one direction), all vertical (in one direction), or a combination of horizontal moves (in one direction) with vertical moves (in one direction).

We examine the cases based on the number of horizontal moves.

**0 horizontal moves**: Since there are \(0\) horizontal moves, there are \(10\) vertical moves. There are two possible endpoints, \((0,10)\) and \((0,-10)\).**1 horizontal move**: Since there is \(1\) horizontal move, there are \(9\) vertical moves. There are four possible endpoints, \((-1,9)\), \((-1,-9)\), \((1,9)\), and \((1,-9)\).**2 horizontal moves**: Since there are \(2\) horizontal moves, there are \(8\) vertical moves. There are four possible endpoints, \((-2,8)\), \((-2,-8)\), \((2,8)\), and \((2,-8)\).**3 horizontal moves**: Since there are \(3\) horizontal moves, there are \(7\) vertical moves. There are four possible endpoints, \((-3,7)\), \((-3,-7)\), \((3,7)\), and \((3,-7)\).**4 horizontal moves**: Since there are \(4\) horizontal moves, there are \(6\) vertical moves. There are four possible endpoints, \((-4,6)\), \((-4,-6)\), \((4,6)\), and \((4,-6)\).**5 horizontal moves**: Since there are \(5\) horizontal moves, there are \(5\) vertical moves. There are four possible endpoints, \((-5,5)\), \((-5,-5)\), \((5,5)\), and \((5,-5)\).**6 horizontal moves**: Since there are \(6\) horizontal moves, there are \(4\) vertical moves. There are four possible endpoints, \((-6,4)\), \((-6,-4)\), \((6,4)\), and \((6,-4)\).**7 horizontal moves**: Since there are \(7\) horizontal moves, there are \(3\) vertical moves. There are four possible endpoints, \((-7,3)\), \((-7,-3)\), \((7,3)\), and \((7,-3)\).**8 horizontal moves**: Since there are \(8\) horizontal moves, there are \(2\) vertical moves. There are four possible endpoints, \((-8,2)\), \((-8,-2)\), \((8,2)\), and \((8,-2)\).**9 horizontal moves**: Since there are \(9\) horizontal moves, there is \(1\) vertical move. There are four possible endpoints, \((-9,1)\), \((-9,-1)\), \((9,1)\), and \((9,-1)\).**10 horizontal moves**: Since there are \(10\) horizontal moves, there are \(0\) vertical moves. There are two possible endpoints, \((-10,0)\) and \((10,0)\).

Therefore, there are a total of \(2 + (4\times 9) +2= 40\) points with integer coordinates that have path distance \(10\) from \(O\).