Difference between revisions of "2014 AIME I Problems/Problem 11"
m (→Solution (casework 2)) |
Smileapple (talk | contribs) m |
||
(2 intermediate revisions by 2 users not shown) | |||
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 1 ( | + | == Solution 1 (Slick Solution) == |
Perform the coordinate transformation <math>(x, y)\rightarrow (x+y, x-y)</math>. Then we can see that a movement up, right, left, or down in the old coordinates adds the vectors <math>\langle 1, -1 \rangle</math>, <math>\langle 1, 1 \rangle</math>, <math>\langle -1, -1 \rangle</math>, <math>\langle -1, 1 \rangle</math> respectively. Moreover, the transformation takes the equation <math>|y| = |x|</math> to the union of the x and y axis. Exactly half of the moves go up in the new coordinates, and half of them go down. In order to end up on the x axis, we need to go up thrice and down thrice. The number of possible sequences of up and down moves is the number of permutations of <math>UUUDDD</math>, which is just <math>\binom63 = 20</math>. The probability of any of these sequences happening is <math>\left(\frac12\right)^6</math>. Thus, the probability of ending on the x axis is <math>\frac{20}{2^6}</math>. Similarly, the probability of ending on the y axis is the same. | Perform the coordinate transformation <math>(x, y)\rightarrow (x+y, x-y)</math>. Then we can see that a movement up, right, left, or down in the old coordinates adds the vectors <math>\langle 1, -1 \rangle</math>, <math>\langle 1, 1 \rangle</math>, <math>\langle -1, -1 \rangle</math>, <math>\langle -1, 1 \rangle</math> respectively. Moreover, the transformation takes the equation <math>|y| = |x|</math> to the union of the x and y axis. Exactly half of the moves go up in the new coordinates, and half of them go down. In order to end up on the x axis, we need to go up thrice and down thrice. The number of possible sequences of up and down moves is the number of permutations of <math>UUUDDD</math>, which is just <math>\binom63 = 20</math>. The probability of any of these sequences happening is <math>\left(\frac12\right)^6</math>. Thus, the probability of ending on the x axis is <math>\frac{20}{2^6}</math>. Similarly, the probability of ending on the y axis is the same. | ||
Line 63: | Line 63: | ||
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> | 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> | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
==Solution 4 (States)== | ==Solution 4 (States)== | ||
Line 108: | Line 97: | ||
<cmath>(0, 0)_6 = \frac{135}{256}</cmath> | <cmath>(0, 0)_6 = \frac{135}{256}</cmath> | ||
Thus, the answer is <math>135 + 256 = \boxed{391}</math>. | Thus, the answer is <math>135 + 256 = \boxed{391}</math>. | ||
+ | |||
+ | ==Solution 5 (Generating Functions)== | ||
+ | For any point <math>(x,y)</math> on the coordinate plane, we can represent it as the term <math>a^xb^y</math>. Then, moving right is equivalent to multiplying by <math>a</math>, moving left is equivalent to multiplying by <math>1/a</math>, and similarly for up/down with <math>b</math> and <math>1/b</math>. Because, on every move, the possibilities are these four directions, and each is equally likely, each move can be represented by multiplying by <math>a+\frac{1}{a}+b+\frac{1}{b}</math>. Thus, the possibilities after <math>6</math> moves are the same as the coefficients of <math>\left(a+\frac{1}{a}+b+\frac{1}{b}\right)^6</math>. By symmetry, we just need to find the number of ways for the token to reach <math>(0,0),(1,1),(2,2),\text{ and }(3,3)</math>. By the multinomial theorem, the coefficient of <math>a^3b^3</math> is <math>\binom{6}{3,3}=20</math>. Similarly, the coefficient of <math>a^2b^2</math> is <math>2\binom{6}{3,2,1}=120</math>. The coefficient of <math>ab</math> is <math>\binom{6}{2,2,1,1}+2\binom{6}{3,2,1}=300</math>. Finally, the constant term is <math>2\binom{6}{2,2,1,1}+2\binom{6}{3,3}=400</math>. Because the total number of possibilities is <math>4^6</math>, the probability is | ||
+ | <cmath>\frac{4(20+120+300)+400}{4^6}=\frac{5+30+75+25}{4^4}=\frac{135}{256},</cmath> | ||
+ | and the answer is <math>391</math>. | ||
+ | --brainiacmaniac31 | ||
+ | |||
== 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}} |
Latest revision as of 22:54, 4 February 2022
Contents
[hide]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 1 (Slick Solution)
Perform the coordinate transformation . Then we can see that a movement up, right, left, or down in the old coordinates adds the vectors , , , respectively. Moreover, the transformation takes the equation to the union of the x and y axis. Exactly half of the moves go up in the new coordinates, and half of them go down. In order to end up on the x axis, we need to go up thrice and down thrice. The number of possible sequences of up and down moves is the number of permutations of , which is just . The probability of any of these sequences happening is . Thus, the probability of ending on the x axis is . Similarly, the probability of ending on the y axis is the same.
However, we overcount exactly one case: ending at . Since ending on the x axis and ending on the y axis are independent events, the probability of both is simply . Using PIE, the total probability is , giving an answer of .
~sampai7
Solution 2 (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 3 (Casework)
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
Solution 4 (States)
Denote the probability that starting from point , the token reaches a point on the graph of in exactly moves. The problem asks us to find . We start by breaking this down: Notice that by symmetry, , so the equation simplifies to We now expand . First, we find . At this point, we can just count the possibilities to find , , and . Therefore, Next, we find . We already calculated , so we just need to find and Therefore, Finally, we find . Putting it all together, Thus, the answer is .
Solution 5 (Generating Functions)
For any point on the coordinate plane, we can represent it as the term . Then, moving right is equivalent to multiplying by , moving left is equivalent to multiplying by , and similarly for up/down with and . Because, on every move, the possibilities are these four directions, and each is equally likely, each move can be represented by multiplying by . Thus, the possibilities after moves are the same as the coefficients of . By symmetry, we just need to find the number of ways for the token to reach . By the multinomial theorem, the coefficient of is . Similarly, the coefficient of is . The coefficient of is . Finally, the constant term is . Because the total number of possibilities is , the probability is and the answer is . --brainiacmaniac31
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.