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 16:13, 20 February 2019 by Syuan01 (talk | contribs) (→‎See also)

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)

We split this into cases by making a chart. In each row, the entries $(\pm1)$ before the dividing line represent the right or left steps (without regard to order), and the entries after the dividing line represent the up or down steps (again, without regard to order). This table only represents the cases where the ending position $(x,y)$ satisfies $x=y$. \[\begin{array}{ccccccccccccl} \multicolumn{5}{c}{R (+)\qquad L (-)}& |&\multicolumn{5}{c}{U (+)\qquad 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 &&(\times 2 \text{ for symmetry by swapping }R-L\text{ and }U-D)\\ \\ +1&& +1 &&+1 &&-1&& -1& |& +1\\ +1&& +1 &&-1&& -1&& -1 &|& -1&& (\times 2\text{ symmetry})\\ \\ +1&& +1 &&+1&& -1&& -1 &&-1&| & (\times2 \text{ symmetry})\\ \end{array}\] Note that to account for the cases when $x=-y$, we can simply multiply the $U-D$ steps by $-1$, so for example, the first row would become \[+1 \qquad+1\qquad +1 \ \ \ \ |\ \ \ -1\qquad -1\qquad -1.\] Therefore, we must multiply the number of possibilities in each case by $2$, except for when $x=y=0$.

Now, we compute the number of possibilities for each case. In particular, we must compute the number of $RLUD$ words, where $R$ represents $+1$ to the left of $|$, $L$ represents $-1$ to the left of $|$, $U$ represents $+1$ to the right of $|$, and $D$ represents $-1$ to the right of $|$. Using multinomials, we compute the following numbers of possibilities for each case. \[{6\choose 3}\cdot 2+ \frac{6!}{2!2!}\cdot 2 + \frac{6!}{2!2!} \cdot 2 + {6\choose 3} \cdot 2 = 2(20 + 180 + 180 + 20) = 800\] \[\frac{6!}{3!2!}\cdot 2 + \frac{6!}{2!2!} + \frac{6!}{3!2!}\cdot 2 = 120 + 180 + 120 = 420\ (\times2\text{ for symmetry})\] \[\frac{6!}{3!2!} \cdot 2 + \frac{6!}{3!2!} \cdot 2 = 120 + 120 = 240\ (\times2\text{ for symmetry})\] \[{6\choose 3} = 20\ (\times 2\text{ for symmetry})\]

Thus, there are $800 + 840 + 480 + 40 = 2160$ possibilities where $|x|=|y|$. Because there are $4^6$ total possibilities, the probability 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 100
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=103637"