Track / Stage 3 / 17 of 260 #17 of 2000

Problem 17

AMC 10/12, early questions

Combinatorics Difficulty 3.0 Find the answer

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?
$\mathrm{(A)}\ 120 \qquad \mathrm{(B)}\ 121 \qquad \mathrm{(C)}\ 221 \qquad \mathrm{(D)}\ 230 \qquad \mathrm{(E)}\ 231$

Your answer

Official solution

Let the starting point be $(0,0)$ . After $10$ steps we can only be in locations $(x,y)$ where $|x|+|y|\leq 10$ . Additionally, each step changes the parity of exactly one coordinate. Hence after $10$ steps we can only be in locations $(x,y)$ where $x+y$ is even. It can easily be shown that each location that satisfies these two conditions is indeed reachable.
Once we pick $x\in\{-10,\dots,10\}$ , we have $11-|x|$ valid choices for $y$ , giving a total of $\boxed{121}$ possible positions.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.