Problem:
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?
Answer Choices:
A.
B.
C.
D.
E.
Solution:
Each step changes either the -coordinate or the -coordinate of the object by 1 . Thus if the object's final point is , then is even and . Conversely, suppose that is a lattice point with . One ten-step path that ends at begins with horizontal steps, to the right if and to the left if . It continues with vertical steps, up if and down if . It has then reached in steps, so it can finish with steps up and steps down. Thus the possible final points are the lattice points that have even coordinate sums and lie on or inside the square with vertices and . There are 11 such points on each of the 11 lines , for a total of different points.
The problems on this page are the property of the MAA's American Mathematics Competitions