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"

(→‎Solution: format)
([texed] solution by ehehheehee)
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>\displaystyle p</math> be the [[probability]] that <math>S_a^{}</math> comes before <math>S_b^{}</math> in alphabetical order. When <math>\displaystyle p</math> is written as a [[fraction]] in [[irreducible fraction|lowest terms]], what is its [[numerator]]?
+
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 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>
Line 21: Line 23:
 
</cmath>
 
</cmath>
  
−
The probability is <math>\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>.
+
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=\boxed{532}/729</math>.
  
 
== See also ==
 
== See also ==

Revision as of 21:39, 11 April 2008

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{tabular}{|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{tabular}\] (Error compiling LaTeX. Unknown error_msg)

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$.

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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1991_AIME_Problems/Problem_10&oldid=24678"