Difference between revisions of "2003 AIME II Problems/Problem 13"

(See also)
(14 intermediate revisions by 8 users not shown)
Line 4: Line 4:
 
== Solution ==
 
== Solution ==
  
===Solution 1===
+
===Solution 1 (Easiest)===
 
Let <math>P_n</math> represent the probability that the bug is at its starting vertex after <math>n</math> moves. If the bug is on its starting vertex after <math>n</math> moves, then it must be not on its starting vertex after <math>n-1</math> moves. At this point it has <math>\frac{1}{2}</math> chance of reaching the starting vertex in the next move. Thus <math>P_n=\frac{1}{2}(1-P_{n-1})</math>.  
 
Let <math>P_n</math> represent the probability that the bug is at its starting vertex after <math>n</math> moves. If the bug is on its starting vertex after <math>n</math> moves, then it must be not on its starting vertex after <math>n-1</math> moves. At this point it has <math>\frac{1}{2}</math> chance of reaching the starting vertex in the next move. Thus <math>P_n=\frac{1}{2}(1-P_{n-1})</math>.  
 
<math>P_0=1</math>, so now we can build it up:
 
<math>P_0=1</math>, so now we can build it up:
Line 19: Line 19:
 
<math>P_{10}=\frac{171}{512}</math>,
 
<math>P_{10}=\frac{171}{512}</math>,
  
Thus the answer is <math>171+512=683</math>
+
Thus the answer is <math>171+512=</math><math>\boxed{683}</math>
  
 
===Solution 2===
 
===Solution 2===
 
Consider there to be a clockwise and a counterclockwise direction around the triangle.  Then, in order for the ant to return to the original vertex, the net number of clockwise steps must be a multiple of 3, i.e., <math>\#CW - \#CCW \equiv 0 \pmod{3}</math>.  Since <math>\#CW + \#CCW = 10</math>, it is only possible that <math>(\#CW,\, \#CCW) = (5,5), (8,2), (2,8)</math>.
 
Consider there to be a clockwise and a counterclockwise direction around the triangle.  Then, in order for the ant to return to the original vertex, the net number of clockwise steps must be a multiple of 3, i.e., <math>\#CW - \#CCW \equiv 0 \pmod{3}</math>.  Since <math>\#CW + \#CCW = 10</math>, it is only possible that <math>(\#CW,\, \#CCW) = (5,5), (8,2), (2,8)</math>.
  
In the first case, we pick <math>5</math> out of the ant's <math>10</math> steps to be clockwise, for a total of <math>{10 \choose 5}</math> paths.  In the second case, we choose <math>8</math> of the steps to be clockwise, and in the third case we choose <math>2</math> to be clockwise.  Hence the total number of ways to return to the original vertex is <math>{10 \choose 5} + {10 \choose 8} + {10 \choose 2} = 252 + 45 + 45 = 342</math>.  Since the ant has two possible steps at each point, there are <math>2^{10}</math> routes the ant can take, and the probability we seek is <math>\frac{342}{2^{10}} = \frac{171}{512}</math>, and the answer is <math>683</math>.
+
In the first case, we pick <math>5</math> out of the ant's <math>10</math> steps to be clockwise, for a total of <math>{10 \choose 5}</math> paths.  In the second case, we choose <math>8</math> of the steps to be clockwise, and in the third case we choose <math>2</math> to be clockwise.  Hence the total number of ways to return to the original vertex is <math>{10 \choose 5} + {10 \choose 8} + {10 \choose 2} = 252 + 45 + 45 = 342</math>.  Since the ant has two possible steps at each point, there are <math>2^{10}</math> routes the ant can take, and the probability we seek is <math>\frac{342}{2^{10}} = \frac{171}{512}</math>, and the answer is <math>\boxed{683}</math>.
  
 
===Solution 3===
 
===Solution 3===
Label the vertices of the triangle <math>A,B,C</math> with the ant starting at <math>A</math>. We will make a table of the number of ways to get to <math>A,B,C</math> in <math>n</math> moves <math>n<=10</math>. The values of the table are calculated from the fact that the number of ways from a vertex say <math>A</math> in <math>n</math> steps equals the number of ways to get to <math>B</math> in <math>n-1</math> steps plus the number of ways to get to <math>C</math> in <math>n-1</math> steps.
+
Label the vertices of the triangle <math>A,B,C</math> with the ant starting at <math>A</math>. We will make a table of the number of ways to get to <math>A,B,C</math> in <math>n</math> moves <math>n\leq10</math>. The values of the table are calculated from the fact that the number of ways from a vertex say <math>A</math> in <math>n</math> steps equals the number of ways to get to <math>B</math> in <math>n-1</math> steps plus the number of ways to get to <math>C</math> in <math>n-1</math> steps.
 +
 
 +
 
 +
 
 +
 
 
<cmath>\begin{array}{|l|ccc|}
 
<cmath>\begin{array}{|l|ccc|}
 
\multicolumn{4}{c}{\text{Table}}\\\hline
 
\multicolumn{4}{c}{\text{Table}}\\\hline
Line 37: Line 41:
 
10 &342 &341 &341 \\\hline
 
10 &342 &341 &341 \\\hline
 
\end{array}</cmath>
 
\end{array}</cmath>
 +
Therefore, our answer is <math>512+171=\boxed{683}.</math>
 +
 +
 +
 +
Notice the pattern that there are <math>\left\lceil\frac{2^n}{3}\right\rceil</math> way to get to <math>A</math> for even <math>n</math> moves. Thus, there are <math>\left\lceil\frac{2^{10}}{3}\right\rceil=342</math> ways.
 +
 +
===Solution 4===
 +
Notice that this problem can be converted into a Markov Chain transition matrix.
 +
 +
The transition matrix is { {0,1,1}, {1,0,1} , {1,1,0} } * (1/2) . Then use the exponentiation method of squaring ( A*A---(A^2)*(A^2)---(A^4*A^4)--(A^8*A^2) to get the transition value of 342. Divide by 2^10 for the probability, reduce fractions, for the result of 171+512 = 683.
 +
 +
===Solution 5 (guess & check)===
 +
This method does not rigorously get the answer, but it works. As the bug makes more and more moves, the probability of it going back to the origin approaches closer and closer to 1/3. Therefore, after 10 moves, the probability gets close to <math>341.33/1024</math>. We can either round up or down. If we round down, we see <math>341/1024</math> cannot be reduced any further and because the only answers on the AIME are below 1000, this cannot be the right answer. However, if we round up, <math>342/1024</math> can be reduced to <math>171/512</math> where the sum 171+512= <math>\boxed{683}</math> is an accepted answer.
 +
 +
===Solution 6 (generating functions)===
 +
The generating function for this is <math>(x+x^2)</math> since an ant on any vertice of the equilateral triangle can go <math>120</math> degrees or <math>240</math> degrees to a side and simplifying <math>(x^{120}+x^{240})</math> gets you <math>(x+x^2)</math>. Since <math>360</math> degrees brings you back to the original vertice then we must find the sum of the coefficients that share a variable with a power divisible by <math>3</math>.
 +
 +
Since we take this rotation <math>10</math> times, our function becomes <math>(x+x^2)^{10}</math> which is the same as <math>x^{10}(x+1)^{10}</math>. This completely simplified is <math>x(x+1)^{10}</math> and since your maximum power is <math>11</math>, we only have to find the coefficients for <math>3</math>, <math>6</math>, and <math>9</math> (<math>0</math> would apply here but the <math>x</math> is the lowest power there is).
 +
 +
For <math>x^9</math>, the coefficient is <math>{10 \choose 2}</math> , and the same goes for <math>x^3</math>. For <math>x^6</math>, the coefficient is <math>{10 \choose 5}</math> and the final sum for the numerator is <math>2*{10 \choose 2} + {10 \choose 5}</math> . The total sum is <math>90+252=342</math> and for the denominator, it was simply <math>2^{10}</math> and this simplified was <math>171/512</math>. Therefore the sum is <math>683</math>.
  
 
== See also ==
 
== See also ==
*[[1985 AIME I Problems/Problem 12]] - very similar problem with a tetrahedron
+
*[[1985 AIME Problems/Problem 12]] - very similar problem with a tetrahedron
  
 
{{AIME box|year=2003|n=II|num-b=12|num-a=14}}
 
{{AIME box|year=2003|n=II|num-b=12|num-a=14}}
 +
 +
[[Category: Intermediate Combinatorics Problems]]
 
{{MAA Notice}}
 
{{MAA Notice}}

Revision as of 00:33, 3 January 2021

Problem

A bug starts at a vertex of an equilateral triangle. On each move, it randomly selects one of the two vertices where it is not currently located, and crawls along a side of the triangle to that vertex. Given that the probability that the bug moves to its starting vertex on its tenth move is $m/n,$ where $m$ and $n$ are relatively prime positive integers, find $m + n.$

Solution

Solution 1 (Easiest)

Let $P_n$ represent the probability that the bug is at its starting vertex after $n$ moves. If the bug is on its starting vertex after $n$ moves, then it must be not on its starting vertex after $n-1$ moves. At this point it has $\frac{1}{2}$ chance of reaching the starting vertex in the next move. Thus $P_n=\frac{1}{2}(1-P_{n-1})$. $P_0=1$, so now we can build it up:

$P_1=0$, $P_2=\frac{1}{2}$, $P_3=\frac{1}{4}$, $P_4=\frac{3}{8}$, $P_5=\frac{5}{16}$, $P_6=\frac{11}{32}$, $P_7=\frac{21}{64}$, $P_8=\frac{43}{128}$, $P_9=\frac{85}{256}$, $P_{10}=\frac{171}{512}$,

Thus the answer is $171+512=$$\boxed{683}$

Solution 2

Consider there to be a clockwise and a counterclockwise direction around the triangle. Then, in order for the ant to return to the original vertex, the net number of clockwise steps must be a multiple of 3, i.e., $\#CW - \#CCW \equiv 0 \pmod{3}$. Since $\#CW + \#CCW = 10$, it is only possible that $(\#CW,\, \#CCW) = (5,5), (8,2), (2,8)$.

In the first case, we pick $5$ out of the ant's $10$ steps to be clockwise, for a total of ${10 \choose 5}$ paths. In the second case, we choose $8$ of the steps to be clockwise, and in the third case we choose $2$ to be clockwise. Hence the total number of ways to return to the original vertex is ${10 \choose 5} + {10 \choose 8} + {10 \choose 2} = 252 + 45 + 45 = 342$. Since the ant has two possible steps at each point, there are $2^{10}$ routes the ant can take, and the probability we seek is $\frac{342}{2^{10}} = \frac{171}{512}$, and the answer is $\boxed{683}$.

Solution 3

Label the vertices of the triangle $A,B,C$ with the ant starting at $A$. We will make a table of the number of ways to get to $A,B,C$ in $n$ moves $n\leq10$. The values of the table are calculated from the fact that the number of ways from a vertex say $A$ in $n$ steps equals the number of ways to get to $B$ in $n-1$ steps plus the number of ways to get to $C$ in $n-1$ steps.



\[\begin{array}{|l|ccc|} \multicolumn{4}{c}{\text{Table}}\\\hline \text{Step}&A&B&C \\\hline 1 &0 &1 &1 \\ 2 &2 &1 &1 \\ 3 &2 &3 &3\\ \vdots &\vdots&\vdots&\vdots \\ 10 &342 &341 &341 \\\hline \end{array}\] Therefore, our answer is $512+171=\boxed{683}.$


Notice the pattern that there are $\left\lceil\frac{2^n}{3}\right\rceil$ way to get to $A$ for even $n$ moves. Thus, there are $\left\lceil\frac{2^{10}}{3}\right\rceil=342$ ways.

Solution 4

Notice that this problem can be converted into a Markov Chain transition matrix.

The transition matrix is { {0,1,1}, {1,0,1} , {1,1,0} } * (1/2) . Then use the exponentiation method of squaring ( A*A---(A^2)*(A^2)---(A^4*A^4)--(A^8*A^2) to get the transition value of 342. Divide by 2^10 for the probability, reduce fractions, for the result of 171+512 = 683.

Solution 5 (guess & check)

This method does not rigorously get the answer, but it works. As the bug makes more and more moves, the probability of it going back to the origin approaches closer and closer to 1/3. Therefore, after 10 moves, the probability gets close to $341.33/1024$. We can either round up or down. If we round down, we see $341/1024$ cannot be reduced any further and because the only answers on the AIME are below 1000, this cannot be the right answer. However, if we round up, $342/1024$ can be reduced to $171/512$ where the sum 171+512= $\boxed{683}$ is an accepted answer.

Solution 6 (generating functions)

The generating function for this is $(x+x^2)$ since an ant on any vertice of the equilateral triangle can go $120$ degrees or $240$ degrees to a side and simplifying $(x^{120}+x^{240})$ gets you $(x+x^2)$. Since $360$ degrees brings you back to the original vertice then we must find the sum of the coefficients that share a variable with a power divisible by $3$.

Since we take this rotation $10$ times, our function becomes $(x+x^2)^{10}$ which is the same as $x^{10}(x+1)^{10}$. This completely simplified is $x(x+1)^{10}$ and since your maximum power is $11$, we only have to find the coefficients for $3$, $6$, and $9$ ($0$ would apply here but the $x$ is the lowest power there is).

For $x^9$, the coefficient is ${10 \choose 2}$ , and the same goes for $x^3$. For $x^6$, the coefficient is ${10 \choose 5}$ and the final sum for the numerator is $2*{10 \choose 2} + {10 \choose 5}$ . The total sum is $90+252=342$ and for the denominator, it was simply $2^{10}$ and this simplified was $171/512$. Therefore the sum is $683$.

See also

2003 AIME II (ProblemsAnswer KeyResources)
Preceded by
Problem 12
Followed by
Problem 14
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