Difference between revisions of "1991 AIME Problems/Problem 10"

m (Solution 1)
Line 7: Line 7:
 
Let us make a chart of values in alphabetical order, where <math>P_a,\ P_b</math> are the probabilities that each string comes from <math>aaa</math> and <math>bbb</math> multiplied by <math>27</math>, and <math>S_b</math> denotes the [[partial sum]]s of <math>P_b</math> (in other words, <math>S_b = \sum_{n=1}^{b} P_b</math>):
 
Let us make a chart of values in alphabetical order, where <math>P_a,\ P_b</math> are the probabilities that each string comes from <math>aaa</math> and <math>bbb</math> multiplied by <math>27</math>, and <math>S_b</math> denotes the [[partial sum]]s of <math>P_b</math> (in other words, <math>S_b = \sum_{n=1}^{b} P_b</math>):
 
<cmath>
 
<cmath>
\begin{tabular}{|r||r|r|r|}
+
\begin{array}{|r||r|r|r|}
 
\hline
 
\hline
 
\text{String}&P_a&P_b&S_b\\
 
\text{String}&P_a&P_b&S_b\\
Line 20: Line 20:
 
bbb & 1 & 8 & 27 \\
 
bbb & 1 & 8 & 27 \\
 
\hline
 
\hline
\end{tabular}  
+
\end{array}  
 
</cmath>
 
</cmath>
  

Revision as of 19:19, 10 March 2015

Problem

Two three-letter strings, $aaa^{}_{}$ and $bbb^{}_{}$, are transmitted electronically. Each string is sent letter by letter. Due to faulty equipment, each of the six letters has a 1/3 chance of being received incorrectly, as an $a^{}_{}$ when it should have been a $b^{}_{}$, or as a $b^{}_{}$ when it should be an $a^{}_{}$. However, whether a given letter is received correctly or incorrectly is independent of the reception of any other letter. Let $S_a^{}$ be the three-letter string received when $aaa^{}_{}$ is transmitted and let $S_b^{}$ be the three-letter string received when $bbb^{}_{}$ is transmitted. Let $p$ be the probability that $S_a^{}$ comes before $S_b^{}$ in alphabetical order. When $p$ is written as a fraction in lowest terms, what is its numerator?

Solution

Solution 1

Let us make a chart of values in alphabetical order, where $P_a,\ P_b$ are the probabilities that each string comes from $aaa$ and $bbb$ multiplied by $27$, and $S_b$ denotes the partial sums of $P_b$ (in other words, $S_b = \sum_{n=1}^{b} P_b$): \[\begin{array}{|r||r|r|r|} \hline \text{String}&P_a&P_b&S_b\\ \hline aaa & 8 & 1 & 1 \\ aab & 4 & 2 & 3 \\ aba & 4 & 2 & 5 \\ abb & 2 & 4 & 9 \\ baa & 4 & 2 & 11 \\ bab & 2 & 4 & 15 \\ bba & 2 & 4 & 19 \\ bbb & 1 & 8 & 27 \\ \hline \end{array}\]

The probability is $p=\sum P_a \cdot (27 - S_b)$, so the answer turns out to be $\frac{8\cdot 26 + 4 \cdot 24 \ldots 2 \cdot 8 + 1 \cdot 0}{27^2} = \frac{532}{729}$, and the solution is $\boxed{532}$.

Solution 2

Let $S(a,n)$ be the $n$th letter of string $S(a)$. Compare the first letter of the string $S(a)$ to the first letter of the string $S(b)$. There is a $(2/3)^2=4/9$ chance that $S(a,1)$ comes before $S(b,1)$. There is a $2(1/3)(2/3)=4/9$ that $S(a,1)$ is the same as $S(b,1)$.

If $S(a,1)=S(b,1)$, then you do the same for the second letters of the strings. But you have to multiply the $4/9$ chance that $S(a,2)$ comes before $S(b,2)$ as there is a $4/9$ chance we will get to this step.

Similarly, if $S(a,2)=S(b,2)$, then there is a $(4/9)^3$ chance that we will get to comparing the third letters and that $S(a)$ comes before $S(b)$.

So we have $p=(4/9)+(4/9)^2+(4/9)^3=4/9+16/81+64/729=\boxed{532}/729$.

Solution 3

Consider $n$ letter strings instead. If the first letters all get transmitted correctly, then the $a$ string will be first. Otherwise, the only way is for both of the first letters to be the same, and then we consider the next $n-1$ letter string following the first letter. This easily leads to a recursion: $p_n=\frac23\cdot\frac23+2\cdot\frac23\cdot\frac13p_{n-1}=\frac49+\frac49p_{n-1}$. Clearly, $p_0=0\implies p_1=\frac49\implies p_2=\frac{52}{81}\implies p_3=\frac{\boxed{532}}{729}$.

See also

1991 AIME (ProblemsAnswer KeyResources)
Preceded by
Problem 9
Followed by
Problem 11
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

Invalid username
Login to AoPS