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 17:31, 15 March 2014
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
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.