Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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

 
m (→‎Solution 1)
 
(10 intermediate revisions by 8 users not shown)
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
 +
Two three-letter strings, <math>aaa^{}_{}</math> and <math>bbb^{}_{}</math>, 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 <math>a^{}_{}</math> when it should have been a <math>b^{}_{}</math>, or as a <math>b^{}_{}</math> when it should be an <math>a^{}_{}</math>. However, whether a given letter is received correctly or incorrectly is independent of the reception of any other letter. Let <math>S_a^{}</math> be the three-letter string received when <math>aaa^{}_{}</math> is transmitted and let <math>S_b^{}</math> be the three-letter string received when <math>bbb^{}_{}</math> is transmitted. Let <math>p</math> be the [[probability]] that <math>S_a^{}</math> comes before <math>S_b^{}</math> in alphabetical order. When <math>p</math> is written as a [[fraction]] in [[irreducible fraction|lowest terms]], what is its [[numerator]]?
 +
 +
__TOC__
  
 
== Solution ==
 
== Solution ==
 +
=== Solution 1 ===
 +
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 sums of <math>P_b</math> (in other words, <math>S_b = \sum_{n=1}^{b} P_b</math>):
 +
<cmath>
 +
\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}
 +
</cmath>
 +
 +
The probability is <math>p=\sum P_a \cdot (27 - S_b)</math>, so the answer turns out to be <math>\frac{8\cdot 26 + 4 \cdot 24 \ldots 2 \cdot 8 + 1 \cdot 0}{27^2} = \frac{532}{729}</math>, and the solution is <math>\boxed{532}</math>.
 +
 +
=== Solution 2 ===
 +
Let <math>S(a,n)</math> be the <math>n</math>th letter of string <math>S(a)</math>.
 +
Compare the first letter of the string <math>S(a)</math> to the first letter of the string <math>S(b)</math>.
 +
There is a <math>(2/3)^2=4/9</math> chance that <math>S(a,1)</math> comes before <math>S(b,1)</math>.
 +
There is a <math>2(1/3)(2/3)=4/9</math> that <math>S(a,1)</math> is the same as <math>S(b,1)</math>.
 +
 +
If <math>S(a,1)=S(b,1)</math>, then you do the same for the second letters of the strings.  But you have to multiply the <math>4/9</math> chance that <math>S(a,2)</math> comes before <math>S(b,2)</math> as there is a <math>4/9</math> chance we will get to this step.
 +
 +
Similarly, if <math>S(a,2)=S(b,2)</math>, then there is a <math>(4/9)^3</math> chance that we will get to comparing the third letters and that <math>S(a)</math> comes before <math>S(b)</math>.
 +
 +
So we have <math>p=(4/9)+(4/9)^2+(4/9)^3=4/9+16/81+64/729=532/729</math>. Therefore, the answer is <math>\boxed{532}</math>.
 +
 +
=== Solution 3 ===
 +
Consider <math>n</math> letter strings instead. If the first letters all get transmitted correctly, then the <math>a</math> 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 <math>n-1</math> letter string following the first letter. This easily leads to a recursion: <math>p_n=\frac23\cdot\frac23+2\cdot\frac23\cdot\frac13p_{n-1}=\frac49+\frac49p_{n-1}</math>. Clearly, <math>p_0=0\implies p_1=\frac49\implies p_2=\frac{52}{81}\implies p_3=\frac{532}{729}</math>. Therefore, the answer is <math>\boxed{532}</math>.
 +
 +
===Solution 4 (a more explicit Solution 3)===
 +
The probability that <math>S_a</math> will take the form <math>a</math> _ _ and that <math>S_b</math> will take the form <math>b</math> _ _ is <math>\frac{2}{3}\cdot\frac{2}{3} = \frac{4}{9}</math>. Then, the probability that both <math>S_a</math> and <math>S_b</math> will share the same first digit is <math>2\cdot\frac{2}{3}\cdot\frac{1}{3} = \frac{4}{9}</math>. Now if the first digits of either sequence are the same, then we must now consider these same probabilities for the second letter of each sequence. The probability that when the first two letters of both sequences are the same, that the second letter of <math>S_a</math> is <math>a</math> and that the second letter of <math>S_b</math> is <math>b</math> is <math>\frac{2}{3}\cdot\frac{2}{3}=\frac{4}{9}</math>. Similarly, the probability that when the first two letters of both sequences are the same, that the second set of letters in both sets of sequences are the same is <math>2\cdot\frac{2}{3}\cdot\frac{1}{3} = \frac{4}{9}</math>. Now, if the last case is true then the probability that <math>S_a</math> precedes <math>S_b</math> is <math>\frac{2}{3}\cdot\frac{2}{3} = \frac{4}{9}</math>. Therefore the total probability would be: <math>\frac{4}{9} + \frac{4}{9}\left(\frac{4}{9} + \frac{4}{9}\left(\frac{4}{9}\right)\right) = \frac{4}{9}+\frac{4}{9}\left(\frac{52}{81}\right) = \frac{4}{9} + \frac{208}{729} = \frac{532}{729}</math>. Therefore the answer is <math>\boxed{532}</math>.
 +
 +
 +
~qwertysri987
  
 
== See also ==
 
== See also ==
−
* [[1991 AIME Problems]]
+
{{AIME box|year=1991|num-b=9|num-a=11}}
 +
 
 +
[[Category:Intermediate Combinatorics Problems]]
 +
{{MAA Notice}}

Latest revision as of 05:10, 25 February 2024

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=532/729$. Therefore, the answer is $\boxed{532}$.

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{532}{729}$. Therefore, the answer is $\boxed{532}$.

Solution 4 (a more explicit Solution 3)

The probability that $S_a$ will take the form $a$ _ _ and that $S_b$ will take the form $b$ _ _ is $\frac{2}{3}\cdot\frac{2}{3} = \frac{4}{9}$. Then, the probability that both $S_a$ and $S_b$ will share the same first digit is $2\cdot\frac{2}{3}\cdot\frac{1}{3} = \frac{4}{9}$. Now if the first digits of either sequence are the same, then we must now consider these same probabilities for the second letter of each sequence. The probability that when the first two letters of both sequences are the same, that the second letter of $S_a$ is $a$ and that the second letter of $S_b$ is $b$ is $\frac{2}{3}\cdot\frac{2}{3}=\frac{4}{9}$. Similarly, the probability that when the first two letters of both sequences are the same, that the second set of letters in both sets of sequences are the same is $2\cdot\frac{2}{3}\cdot\frac{1}{3} = \frac{4}{9}$. Now, if the last case is true then the probability that $S_a$ precedes $S_b$ is $\frac{2}{3}\cdot\frac{2}{3} = \frac{4}{9}$. Therefore the total probability would be: $\frac{4}{9} + \frac{4}{9}\left(\frac{4}{9} + \frac{4}{9}\left(\frac{4}{9}\right)\right) = \frac{4}{9}+\frac{4}{9}\left(\frac{52}{81}\right) = \frac{4}{9} + \frac{208}{729} = \frac{532}{729}$. Therefore the answer is $\boxed{532}$.


~qwertysri987

See also

1991 AIME (Problems • Answer Key • Resources)
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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1991_AIME_Problems/Problem_10&oldid=216199"