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> | + | 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, and , 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 when it should have been a , or as a when it should be an . However, whether a given letter is received correctly or incorrectly is independent of the reception of any other letter. Let be the three-letter string received when is transmitted and let be the three-letter string received when is transmitted. Let be the probability that comes before in alphabetical order. When 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 are the probabilities that each string comes from and multiplied by , and denotes the partial sums of (in other words, ):
\[\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 , so the answer turns out to be , and the solution is .
Solution 2
Let be the th letter of string . Compare the first letter of the string to the first letter of the string . There is a chance that comes before . There is a that is the same as .
If , then you do the same for the second letters of the strings. But you have to multiply the chance that comes before as there is a chance we will get to this step.
Similarly, if , then there is a chance that we will get to comparing the third letters and that comes before .
So we have .
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 |