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

2014 AIME I Problems/Problem 11

Revision as of 20:37, 22 March 2014 by Suli (talk | contribs) (→‎Solution (casework))

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}.$

Solution (casework 2)

Make a chart:

R (+) L (-) | U (+) D (-) +1 +1 +1 | +1 +1 + 1 +1 +1 -1 | +1 +1 -1 +1 -1 -1 | +1 -1 -1 -1 -1 -1 | -1 -1 -1

+1 +1 +1 -1 | +1 +1 +1 +1 -1 -1 | +1 -1 +1 -1 -1 -1 | -1 -1 (x2 symmetry by swapping R-L and U-D)

+1 +1 +1 -1 -1 | +1 +1 +1 -1 -1 -1 | -1 (x2 symmetry)

+1 +1 +1 -1 -1 -1 | (x2 symmetry)

Note we have to multiply by two to account for cases like +1 +1 +1 | -1 -1 -1.

Now, we use multinomials and do the arithmetic: 

     6C3 * 2 + 6!/(2!2!) * 2 + 6!/(2!2!) * 2 + 6C3 * 2 = 2(20 + 180 + 180 + 20) = 800
     6!/(3!2!) * 2 + 6!/(2!2!) + 6!/(3!2!)) * 2 = 120 + 180 + 120 = 420 (x2)
     6!/(3!2!) * 2 + 6!/(3!2!) * 2 = 120 + 120 = 240 (x2)
     6C3 = 20 (x2)

Thus, there are 800 + 840 + 480 + 40 = 2160 cases. Because there is $4^6$ total cases, the answer is $\frac{2160}{4^6} = \frac{135}{256}$, so the answer is $\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=61148"