Welcome to our community

Be a part of something great, join today!

Problem Of The Week #432 August 31st, 2020

Status
Not open for further replies.
  • Thread starter
  • Admin
  • #1

anemone

MHB POTW Director
Staff member
Feb 14, 2012
3,894
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?

-----

Remember to read the POTW submission guidelines to find out how to submit your answers!
 
  • Thread starter
  • Admin
  • #2

anemone

MHB POTW Director
Staff member
Feb 14, 2012
3,894
No one answered last week's POTW. (Sadface) However, you can find the suggested solution as follows:
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.
 
Status
Not open for further replies.