Difference between revisions of "2014 AIME I Problems/Problem 11"
m (→Solution (casework 2)) |
Mathgeek2006 (talk | contribs) m (→Solution (casework 2)) |
||
Line 27: | Line 27: | ||
==Solution (casework 2)== | ==Solution (casework 2)== | ||
− | + | We split this into cases by making a chart. In each row, the entries <math>(\pm1)</math> 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 <math>(x,y)</math> satisfies <math>x=y</math>. | |
+ | <cmath> | ||
+ | \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} | ||
+ | </cmath> | ||
+ | Note that to account for the cases when <math>x=-y</math>, we can simply multiply the <math>U-D</math> steps by <math>-1</math>, so for example, the first row would become <cmath>+1 \qquad+1\qquad +1 \ \ \ \ |\ \ \ -1\qquad -1\qquad -1.</cmath> Therefore, we must multiply the number of possibilities in each case by <math>2</math>, except for when <math>x=y=0</math>. | ||
− | + | Now, we compute the number of possibilities for each case. In particular, we must compute the number of <math>RLUD</math> words, where <math>R</math> represents <math>+1</math> to the left of <math>|</math>, <math>L</math> represents <math>-1</math> to the left of <math>|</math>, <math>U</math> represents <math>+1</math> to the right of <math>|</math>, and <math>D</math> represents <math>-1</math> to the right of <math>|</math>. Using multinomials, we compute the following numbers of possibilities for each case. | |
− | + | + | <cmath>{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</cmath> |
− | + | <cmath>\frac{6!}{3!2!}\cdot 2 + \frac{6!}{2!2!} + \frac{6!}{3!2!}\cdot 2 = 120 + 180 + 120 = 420\ (\times2\text{ for symmetry})</cmath> | |
− | + | <cmath>\frac{6!}{3!2!} \cdot 2 + \frac{6!}{3!2!} \cdot 2 = 120 + 120 = 240\ (\times2\text{ for symmetry})</cmath> | |
− | + | <cmath>{6\choose 3} = 20\ (\times 2\text{ for symmetry})</cmath> | |
− | + | Thus, there are <math>800 + 840 + 480 + 40 = 2160</math> possibilities where <math>|x|=|y|</math>. Because there are <math>4^6</math> total possibilities, the probability is <math>\frac{2160}{4^6} = \frac{135}{256}</math>, so the answer is <math>\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:35, 13 March 2015
Problem 11
A token starts at the point of an -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 is , where and are relatively prime positive integers. Find .
Solution (casework)
We have 4 possible moves: U, D, R, and L. The total number of paths that could be taken is , or . There are 4 possible cases that land along the line : or . We will count the number of ways to end up at and , multiply them by 4 to account for the other quadrants, and add this to the number of ways to end up at .
- Case 1: The token ends at . 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 , which is
- Case 2: The token ends at . 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 and , both of which are , for a total of possibilities.
- Case 3: The token ends at . 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 is
- 1 up move, 3 right moves, and 2 left moves. In this case, the number of ways to rearrange the letters in the sequence is
- 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 is
Thus, the total number of ways to end up at is .
- Case 4: The token ends at . 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 is
- 3 up moves and 3 down moves. In this case, the number of ways to rearrange the letters in the sequence is
- 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 is
- 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 is
Thus, the total number of ways to end up at is .
Adding these cases together, we get that the total number of ways to end up on is . Thus, our probability is . When this fraction is fully reduced, it is , so our answer is
Solution (casework 2)
We split this into cases by making a chart. In each row, the entries 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 satisfies . Note that to account for the cases when , we can simply multiply the steps by , so for example, the first row would become Therefore, we must multiply the number of possibilities in each case by , except for when .
Now, we compute the number of possibilities for each case. In particular, we must compute the number of words, where represents to the left of , represents to the left of , represents to the right of , and represents to the right of . Using multinomials, we compute the following numbers of possibilities for each case.
Thus, there are possibilities where . Because there are total possibilities, the probability is , so the answer is
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.