Difference between revisions of "1991 AIME Problems/Problem 10"
([texed] solution by ehehheehee) |
(→Solution) |
||
Line 36: | Line 36: | ||
So we have <math>p=(4/9)+(4/9)^2+(4/9)^3=4/9+16/81+64/729=\boxed{532}/729</math>. | So we have <math>p=(4/9)+(4/9)^2+(4/9)^3=4/9+16/81+64/729=\boxed{532}/729</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{\boxed{532}}{729}</math>. | ||
== See also == | == See also == |
Revision as of 19:07, 24 March 2009
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 .
Solution 3
Consider letter strings instead. If the first letters all get transmitted correctly, then the
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
letter string following the first letter. This easily leads to a recursion:
. Clearly,
.
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 |