# Problem of the Week Problem E and Solution The Shortest Path

## Problem

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

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$$.