Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2006 AMC 12B Problems/Problem 18"
(→‎Solution)
 
(11 intermediate revisions by 7 users not shown)
Line 1: Line 1:
 
== Problem ==
 
== 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?
  
−
== Solution ==
+
<math>
 +
\mathrm{(A)}\ 120
 +
\qquad
 +
\mathrm{(B)}\ 121
 +
\qquad
 +
\mathrm{(C)}\ 221
 +
\qquad
 +
\mathrm{(D)}\ 230
 +
\qquad
 +
\mathrm{(E)}\ 231
 +
</math>
 +
 
 +
== Solution 1 ==
 +
 
 +
Let the starting point be <math>(0,0)</math>. After <math>10</math> steps we can only be in locations <math>(x,y)</math> where <math>|x|+|y|\leq 10</math>. Additionally, each step changes the [[parity]] of exactly one coordinate. Hence after <math>10</math> steps we can only be in locations <math>(x,y)</math> where <math>x+y</math> is even. It can easily be shown that each location that satisfies these two conditions is indeed reachable.
 +
 
 +
Once we pick <math>x\in\{-10,\dots,10\}</math>, we have <math>11-|x|</math> valid choices for <math>y</math>, giving a total of <math>\boxed{121}</math> possible positions.
 +
 
 +
==Solution 2==
 +
 
 +
<math>10</math> moves results in a lot of possible endpoints, so we try small cases first.
 +
 
 +
If the object only makes <math>1</math> move, it is obvious that there are only 4 possible points that the object can move to.
 +
If the object makes <math>2</math> moves, it can move to <math>(0, 2)</math>, <math>(1, 1)</math>, <math>(2, 0)</math>, <math>(1, -1)</math>, <math>(0, -2)</math>, <math>(-1, -1)</math>, <math>(-2, 0)</math> as well as <math>(0, 0)</math>, for a total of <math>9</math> moves.
 +
If the object makes <math>3</math> moves, it can end up at <math>(0, 3)</math>, <math>(2, 1)</math>, <math>(1, 2)</math>, <math>(3, 0)</math>, <math>(2, -1)</math>, <math>(1, -2)</math>, <math>(0, -3)</math>, <math>(-1, -2)</math>, <math>(-2, -1)</math>, <math>(0, -3)</math> etc. for a total of <math>16</math> moves.
 +
 
 +
At this point we can guess that for n moves, there are <math>(n + 1)^2</math> different endpoints. Thus, for 10 moves, there are <math>11^2 = 121</math> endpoints, and the answer is <math>\boxed{B}</math>.
  
 
== See also ==
 
== See also ==
−
* [[2006 AMC 12B Problems]]
+
{{AMC12 box|year=2006|ab=B|num-b=17|num-a=19}}
 +
{{MAA Notice}}

Latest revision as of 15:57, 28 December 2020

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?

$\mathrm{(A)}\ 120 \qquad \mathrm{(B)}\ 121 \qquad \mathrm{(C)}\ 221 \qquad \mathrm{(D)}\ 230 \qquad \mathrm{(E)}\ 231$

Solution 1

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.

Solution 2

$10$ moves results in a lot of possible endpoints, so we try small cases first.

If the object only makes $1$ move, it is obvious that there are only 4 possible points that the object can move to. If the object makes $2$ moves, it can move to $(0, 2)$, $(1, 1)$, $(2, 0)$, $(1, -1)$, $(0, -2)$, $(-1, -1)$, $(-2, 0)$ as well as $(0, 0)$, for a total of $9$ moves. If the object makes $3$ moves, it can end up at $(0, 3)$, $(2, 1)$, $(1, 2)$, $(3, 0)$, $(2, -1)$, $(1, -2)$, $(0, -3)$, $(-1, -2)$, $(-2, -1)$, $(0, -3)$ etc. for a total of $16$ moves.

At this point we can guess that for n moves, there are $(n + 1)^2$ different endpoints. Thus, for 10 moves, there are $11^2 = 121$ endpoints, and the answer is $\boxed{B}$.

See also

2006 AMC 12B (Problems • Answer Key • Resources)
Preceded by
Problem 17 		Followed by
Problem 19
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25
All AMC 12 Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2006_AMC_12B_Problems/Problem_18&oldid=140852"