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 "2014 AIME I Problems/Problem 11"

(→‎Problem 11)
(→‎Solution)
Line 3: Line 3:
 
A token starts at the point <math>(0,0)</math> of an <math>xy</math>-coordinate grid and then makes a sequence of six moves. Each move is 1 unit in a direction parallel to one of the coordinate axes. Each move is selected randomly from the four possible directions and independently of the other moves. The probability the token ends at a point on the graph of <math>|y|=|x|</math> is <math>\frac{m}{n}</math>, where <math>m</math> and <math>n</math> are relatively prime positive integers. Find <math>m+n</math>.
 
A token starts at the point <math>(0,0)</math> of an <math>xy</math>-coordinate grid and then makes a sequence of six moves. Each move is 1 unit in a direction parallel to one of the coordinate axes. Each move is selected randomly from the four possible directions and independently of the other moves. The probability the token ends at a point on the graph of <math>|y|=|x|</math> is <math>\frac{m}{n}</math>, where <math>m</math> and <math>n</math> are relatively prime positive integers. Find <math>m+n</math>.
  
−
== Solution ==
+
== Solution (casework) ==
 +
 
 +
We have 4 possible moves: U, D, R, and L. The total number of paths that could be taken is <math>4^6</math>, or <math>4096</math>. There are 4 possible cases that land along the line <math>y = x</math>: <math>x,y = \pm 1; x,y = \pm 2; x,y = \pm 3;</math> or <math>x = y = 0</math>. We will count the number of ways to end up at <math>(1,1), (2,2),</math> and <math>(3,3)</math>, multiply them by 4 to account for the other quadrants, and add this to the number of ways to end up at <math>(0,0)</math>.
 +
 
 +
*Case 1: The token ends at <math>(3, 3)</math>. In order for the token to end up here, it must have had 3 right moves, and 3 up moves. In other words, the total number of ways to get here is the ways to rearrange the letters in the sequence <math>RRRUUU</math>, which is <math>{6\choose 3} = 20.</math>
 +
 
 +
*Case 2: The token ends at <math>(2,2)</math>. In order for the token to end up here, it could have had 2 up moves, 3 right moves, and 1 left move; or 2 right moves, 3 up moves, and 1 down move. Thus, the total number of ways to get here is sum of the ways to rearrange the letters in the sequences <math>RRRLUU</math> and <math>UUUDRR</math>, both of which are <math>{6\choose 1}{5\choose 2} = 60</math>, for a total of <math>120</math> possibilities.
 +
 
 +
*Case 3: The token ends at <math>(1,1)</math>. In order for the token to end up here, it could have had:
 +
**1 right move, 3 up moves, and 2 down moves. In this case, the number of ways to rearrange the letters in the sequence <math>RUUUDD</math> is <math>{6\choose 1}{5\choose 2} = 60.</math>
 +
**1 up move, 3 right moves, and 2 left moves. In this case, the number of ways to rearrange the letters in the sequence <math>URRRLL</math> is <math>{6\choose 1}{5\choose 2} = 60.</math>
 +
**2 right moves, 1 left move, 2 up moves, and 1 down move. In this case, the number of ways to rearrange the letters in the sequence <math>UUDRRL</math> is <math>{6\choose 1}{5\choose 1}{4\choose 2} = 180.</math>
 +
Thus, the total number of ways to end up at <math>(1,1)</math> is <math>300</math>.
 +
 
 +
*Case 4: The token ends at <math>(0,0)</math>. In order for the token to end up here, it could have had:
 +
**3 right moves and 3 left moves. In this case, the number of ways to rearrange the letters in the sequence <math>RRRLLL</math> is <math>{6\choose 3} = 20.</math>
 +
**3 up moves and 3 down moves. In this case, the number of ways to rearrange the letters in the sequence <math>UUUDDD</math> is <math>{6\choose 3} = 20.</math>
 +
**1 right move, 1 left move, 2 up moves, and 2 down moves. In this case, the number of ways to rearrange the letters in the sequence <math>RLUUDD</math> is <math>{6\choose 1}{5\choose 1}{4\choose 2} = 180.</math>
 +
**1 up move, 1 down move, 2 right moves, and 2 left moves. In this case, the number of ways to rearrange the letters in the sequence <math>RRLLUD</math> is <math>{6\choose 1}{5\choose 1}{4\choose 2} = 180.</math>
 +
Thus, the total number of ways to end up at <math>(0,0)</math> is <math>400</math>.
 +
 
 +
Adding these cases together, we get that the total number of ways to end up on <math>y = x</math> is <math>4(20 + 120 + 300) + 400 = 2160</math>. Thus, our probability is <math>\frac{2160}{4096}</math>. When this fraction is fully reduced, it is <math>\frac{135}{256}</math>, so our answer is <math>135 + 256 = \boxed{391}.</math>
  
 
== See also ==
 
== See also ==
 
{{AIME box|year=2014|n=I|num-b=10|num-a=12}}
 
{{AIME box|year=2014|n=I|num-b=10|num-a=12}}
 
{{MAA Notice}}
 
{{MAA Notice}}

Revision as of 18:31, 15 March 2014

Problem 11

A token starts at the point $(0,0)$ of an $xy$-coordinate grid and then makes a sequence of six moves. Each move is 1 unit in a direction parallel to one of the coordinate axes. Each move is selected randomly from the four possible directions and independently of the other moves. The probability the token ends at a point on the graph of $|y|=|x|$ is $\frac{m}{n}$, where $m$ and $n$ are relatively prime positive integers. Find $m+n$.

Solution (casework)

We have 4 possible moves: U, D, R, and L. The total number of paths that could be taken is $4^6$, or $4096$. There are 4 possible cases that land along the line $y = x$: $x,y = \pm 1; x,y = \pm 2; x,y = \pm 3;$ or $x = y = 0$. We will count the number of ways to end up at $(1,1), (2,2),$ and $(3,3)$, multiply them by 4 to account for the other quadrants, and add this to the number of ways to end up at $(0,0)$.

  • Case 1: The token ends at $(3, 3)$. In order for the token to end up here, it must have had 3 right moves, and 3 up moves. In other words, the total number of ways to get here is the ways to rearrange the letters in the sequence $RRRUUU$, which is ${6\choose 3} = 20.$
  • Case 2: The token ends at $(2,2)$. In order for the token to end up here, it could have had 2 up moves, 3 right moves, and 1 left move; or 2 right moves, 3 up moves, and 1 down move. Thus, the total number of ways to get here is sum of the ways to rearrange the letters in the sequences $RRRLUU$ and $UUUDRR$, both of which are ${6\choose 1}{5\choose 2} = 60$, for a total of $120$ possibilities.
  • Case 3: The token ends at $(1,1)$. In order for the token to end up here, it could have had:
    • 1 right move, 3 up moves, and 2 down moves. In this case, the number of ways to rearrange the letters in the sequence $RUUUDD$ is ${6\choose 1}{5\choose 2} = 60.$
    • 1 up move, 3 right moves, and 2 left moves. In this case, the number of ways to rearrange the letters in the sequence $URRRLL$ is ${6\choose 1}{5\choose 2} = 60.$
    • 2 right moves, 1 left move, 2 up moves, and 1 down move. In this case, the number of ways to rearrange the letters in the sequence $UUDRRL$ is ${6\choose 1}{5\choose 1}{4\choose 2} = 180.$

Thus, the total number of ways to end up at $(1,1)$ is $300$.

  • Case 4: The token ends at $(0,0)$. In order for the token to end up here, it could have had:
    • 3 right moves and 3 left moves. In this case, the number of ways to rearrange the letters in the sequence $RRRLLL$ is ${6\choose 3} = 20.$
    • 3 up moves and 3 down moves. In this case, the number of ways to rearrange the letters in the sequence $UUUDDD$ is ${6\choose 3} = 20.$
    • 1 right move, 1 left move, 2 up moves, and 2 down moves. In this case, the number of ways to rearrange the letters in the sequence $RLUUDD$ is ${6\choose 1}{5\choose 1}{4\choose 2} = 180.$
    • 1 up move, 1 down move, 2 right moves, and 2 left moves. In this case, the number of ways to rearrange the letters in the sequence $RRLLUD$ is ${6\choose 1}{5\choose 1}{4\choose 2} = 180.$

Thus, the total number of ways to end up at $(0,0)$ is $400$.

Adding these cases together, we get that the total number of ways to end up on $y = x$ is $4(20 + 120 + 300) + 400 = 2160$. Thus, our probability is $\frac{2160}{4096}$. When this fraction is fully reduced, it is $\frac{135}{256}$, so our answer is $135 + 256 = \boxed{391}.$

See also

2014 AIME I (Problems • Answer Key • Resources)
Preceded by
Problem 10 		Followed by
Problem 12
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME 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=2014_AIME_I_Problems/Problem_11&oldid=61072"