Difference between revisions of "2014 AIME I Problems/Problem 11"
(Created page with "== Problem 11 == == Solution ==") |
Smileapple (talk | contribs) m |
||
(28 intermediate revisions by 12 users not shown) | |||
Line 1: | Line 1: | ||
== Problem 11 == | == Problem 11 == | ||
− | == Solution == | + | 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 (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. | ||
+ | |||
+ | However, we overcount exactly one case: ending at <math>(0, 0)</math>. Since ending on the x axis and ending on the y axis are independent events, the probability of both is simply <math>\left(\frac{20}{2^6}\right)^2 = \frac{25}{256}</math>. Using PIE, the total probability is <math>\frac{20}{64} + \frac{20}{64} - \frac{25}{256} = \frac{135}{256}</math>, giving an answer of <math>\boxed{391}</math>. | ||
+ | |||
+ | ~sampai7 | ||
+ | |||
+ | |||
+ | == Solution 2 (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> | ||
+ | |||
+ | ==Solution 3 (Casework)== | ||
+ | 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> | ||
+ | |||
+ | ==Solution 4 (States)== | ||
+ | Denote <math>(x, y)_n</math> the probability that starting from point <math>(x, y)</math>, the token reaches a point on the graph of <math>|y| = |x|</math> in exactly <math>n</math> moves. The problem asks us to find <math>(0, 0)_6</math>. We start by breaking this down: | ||
+ | <cmath>(0, 0)_6 = \frac14 \cdot ((0, 1)_5 + (0, -1)_5 + (1, 0)_5 + (-1, 0)_5)</cmath> | ||
+ | Notice that by symmetry, <math>(0, 1)_5 = (0, -1)_5 = (1, 0)_5 = (-1, 0)_5</math>, so the equation simplifies to | ||
+ | <cmath>(0, 0)_6 = (0, 1)_5</cmath> | ||
+ | We now expand <math>(0, 1)_5</math>. | ||
+ | <cmath>(0, 1)_5 = \frac14 \cdot ((0, 0)_4 + (0, 2)_4 + 2(1, 1)_4)</cmath> | ||
+ | First, we find <math>(0, 0)_4</math>. | ||
+ | <cmath>(0, 0)_4 = (0, 1)_3</cmath> | ||
+ | <cmath>(0, 1)_3 = \frac14 \cdot ((0, 0)_2 + (0, 2)_2 + 2(1, 1)_2)</cmath> | ||
+ | At this point, we can just count the possibilities to find <math>(0, 0)_2 = \frac34</math>, <math>(0, 2)_2 = \frac{7}{16}</math>, and <math>(1, 1)_2 = \frac58</math>. Therefore, | ||
+ | <cmath>(0, 1)_3 = \frac14 \cdot (\frac34 + \frac{7}{16} + 2 \cdot \frac58)</cmath> | ||
+ | <cmath>(0, 1)_3 = \frac{39}{64}</cmath> | ||
+ | Next, we find <math>(0, 2)_4</math>. | ||
+ | <cmath>(0, 2)_4 = \frac14 \cdot ((0, 1)_3 + (0, 3)_3 + 2(1, 2)_3)</cmath> | ||
+ | We already calculated <math>(0, 1)_3</math>, so we just need to find <math>(0, 3)_3</math> and <math>(1, 2)_3</math> | ||
+ | <cmath>(0, 3)_3 = \frac14 \cdot ((0, 2)_2 + (0, 4)_2 + 2(1, 3)_2)</cmath> | ||
+ | <cmath>(0, 3)_3 = \frac14 \cdot (\frac{7}{16} + 0 + 2 \cdot \frac{1}{4})</cmath> | ||
+ | <cmath>(0, 3)_3 = \frac{15}{64}</cmath> | ||
+ | <cmath>(1, 2)_3 = \frac14 \cdot ((1, 3)_2 + (1, 1)_2 + (0, 2)_2 + (2, 2)_2)</cmath> | ||
+ | <cmath>(1, 2)_3 = \frac14 \cdot (\frac14 + \frac58 + \frac{7}{16} + \frac12)</cmath> | ||
+ | <cmath>(1, 2)_3 = \frac{29}{64}</cmath> | ||
+ | Therefore, | ||
+ | <cmath>(0, 2)_4 = \frac14 \cdot (\frac{39}{64} + \frac{15}{64} + 2 \cdot \frac{29}{64})</cmath> | ||
+ | <cmath>(0, 2)_4 = \frac{7}{16}</cmath> | ||
+ | Finally, we find <math>(1, 1)_4</math>. | ||
+ | <cmath>(1, 1)_4 = \frac12 \cdot ((0, 1)_3 + (1, 2)_3)</cmath> | ||
+ | <cmath>(1, 1)_4 = \frac12 \cdot (\frac{39}{64} + \frac{29}{64})</cmath> | ||
+ | <cmath>(1, 1)_4 = \frac{17}{32}</cmath> | ||
+ | Putting it all together, | ||
+ | <cmath>(0, 0)_6 = (0, 1)_5 =\frac14 \cdot (\frac{39}{64} + \frac{7}{16} + 2 \cdot \frac{17}{32})</cmath> | ||
+ | <cmath>(0, 0)_6 = \frac{135}{256}</cmath> | ||
+ | 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 == | ||
+ | {{AIME box|year=2014|n=I|num-b=10|num-a=12}} | ||
+ | {{MAA Notice}} |
Latest revision as of 23:54, 4 February 2022
Contents
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
- 1 right move, 3 up moves, and 2 down moves. In this case, the number of ways to rearrange the letters in the sequence
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
- 3 right moves and 3 left moves. In this case, the number of ways to rearrange the letters in the sequence
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.