# Problem Of The Week #432 August 31st, 2020

Status
Not open for further replies.

#### anemone

##### MHB POTW Director
Staff member
Here is this week's POTW:

-----

An object in the plane moves from one lattice point to another. At each step, the object may move one unit to the right, one unit to the left, one unit up, or one unit down. If the object starts at the origin and takes a ten-step path, how many different points could be the final point?

-----

Each step changes either the $x$-coordinate or the $y$-coordinate of the object by 1. Thus if the object’s final point is $(a,\,b)$, then $a+b$ is even and $|a|+|b|\le10$. Conversely, suppose that $(a,\,b)$ is a lattice point with $|a|+|b|= 2k\le10$. One ten-step path that ends at $(a,\,b)$ begins with $|a|$ horizontal steps, to the right if $a\ge 0$ and to the left if $a <0$. It continues with $|b|$ vertical steps, up if $b\ge 0$ and down if $b <0$. It has then reached $(a,\,b)$ in 2k steps, so it can finish with 5−k steps up and 5−k steps down. Thus the possible final points are the lattice points that have even coordinate sums and lie on or inside the squarewith vertices $(\pm10,0)$ and $(0,\pm 10)$. There are 11 such points on each of the 11 lines $x+y= 2k$, $−5\le k \le 5$, for a total of 121 different points.