Difference between revisions of "1995 AIME Problems/Problem 15"
(→Solution) |
|||
| Line 19: | Line 19: | ||
The answer is <math>p_H + p_T = \frac{3}{2}p_H = \frac{3}{34}</math>, and <math>m+n = \boxed{037}</math>. | The answer is <math>p_H + p_T = \frac{3}{2}p_H = \frac{3}{34}</math>, and <math>m+n = \boxed{037}</math>. | ||
| + | |||
| + | === Solution 3 === | ||
| + | For simplicity, let's compute the complement, namely the probability of getting to <math>2</math> tails before <math>5</math> heads. | ||
| + | |||
| + | Let <math>h_{i}</math> denote the probability that we get <math>2</math> tails before <math>5</math> heads, given that we have <math>i</math> consecutive heads. Similarly, let <math>t_{i}</math> denote the probability that we get <math>2</math> tails before <math>5</math> heads, given that we have <math>i</math> consecutive tails. Specifically, <math>h_{5} = 0</math> and <math>t_{2} = 1</math>. If we can solve for <math>h_{1}</math> and <math>t_{1}</math>, we are done; the answer is simply <math>1/2 * (h_{1} + t_{1})</math>, since on our first roll, we have equal chances of getting a string with "1 consecutive head" or "1 consecutive tail." | ||
| + | |||
| + | Consider solving for <math>t_{1}</math>. If we have 1 consecutive tail, then (a) rolling a head gets us to 1 consecutive head and (b) rolling a tail gets us to 2 consecutive tails. So, we must have: | ||
| + | |||
| + | <center> | ||
| + | <math>t_{1} = \frac{1}{2} t_{2} + \frac{1}{2} h_{1}</math> | ||
| + | </center> | ||
| + | |||
| + | Applying similar logic, we get the equations: | ||
| + | |||
| + | <cmath>\begin{align*} | ||
| + | h_{1} &= \frac{1}{2} h_{2} + \frac{1}{2} t_{1}\\ | ||
| + | h_{2} &= \frac{1}{2} h_{3} + \frac{1}{2} t_{1}\\ | ||
| + | h_{3} &= \frac{1}{2} h_{4} + \frac{1}{2} t_{1}\\ | ||
| + | h_{4} &= \frac{1}{2} h_{5} + \frac{1}{2} t_{1} | ||
| + | \end{align*}</cmath> | ||
| + | |||
| + | Since <math>h_{5} = 0</math>, we get <math>h_{4} = \frac{1}{2} t_{1}</math> <math>\Rightarrow h_{3} = \frac{3}{4} t_{1}</math> <math>\Rightarrow h_{2} = \frac{7}{8} t_{1}</math> <math>\Rightarrow h_{1} = \frac{15}{16} t_{1}</math> <math>\Rightarrow t_{1} = \frac{1}{2} t_{2} + \frac{1}{2} \cdot \frac{15}{16} t_{1} = \frac{1}{2} + \frac{15}{32} t_{1} \Rightarrow t_{1} = \frac{16}{17}</math> <math>\Rightarrow h_{1} = \frac{15}{16} \frac{16}{17} = \frac{15}{17}</math>. | ||
| + | |||
| + | So, the probability of reaching <math>2</math> tails before <math>5</math> heads is <math>\frac{1}{2} (h_{1} + t_{1}) = \frac{31}{34}</math>; we want the complement, <math>\frac{3}{34}</math>, yielding an answer of <math>3 + 34 = \boxed{37}</math>. | ||
| + | |||
| + | Note: the same approach still works if we tried solving the original problem rather than the complement; we would have simply used <math>h_{5} = 1</math> and <math>t_{2} = 0</math> instead. The repeated back-substitution is cleaner because we used the complement. | ||
== See also == | == See also == | ||
Revision as of 19:45, 6 October 2014
Problem
Let 
be the probability that, in the process of repeatedly flipping a fair coin, one will encounter a run of 
heads before one encounters a run of 
tails. Given that can be written in the form 
where 
and 
are relatively prime positive integers, find 
.
Solution
Solution 1
Think of the problem as a sequence of H's and T's. No two T's can occur in a row, so the sequence is blocks of 
to 
H's separated by T's and ending in H's. Since the first letter could be T or the sequence could start with a block of H's, the total probability is 
that of it had to start with and H.
The answer to the problem is then the sum of all numbers of the form 
, where 
are all numbers 
, since the blocks of H's can range from in length. The sum of all numbers of the form 
is 
, so if there are n blocks of H's before the final five H's, the answer can be rewritten as the sum of all numbers of the form 
, where 
ranges from 
to 
, since that's how many blocks of H's there can be before the final five. This is an infinite geometric series whose sum is 
, so the answer is 
.
Solution 2
Let 
respectively denote the probabilities that a string of H's and T's are successful. A successful string can either start with H, or it can start with T and then continue with a string starting with H (as there cannot be T's in a row). Thus
A successful string starting with H must start with a block of 
H's, then a T, then a successful string starting with H, or reach a block of H's. Thus,
The answer is 
, and 
.
Solution 3
For simplicity, let's compute the complement, namely the probability of getting to tails before heads.
Let 
denote the probability that we get tails before heads, given that we have 
consecutive heads. Similarly, let 
denote the probability that we get tails before heads, given that we have consecutive tails. Specifically, 
and 
. If we can solve for 
and 
, we are done; the answer is simply 
, since on our first roll, we have equal chances of getting a string with "1 consecutive head" or "1 consecutive tail."
Consider solving for . If we have 1 consecutive tail, then (a) rolling a head gets us to 1 consecutive head and (b) rolling a tail gets us to 2 consecutive tails. So, we must have:
Applying similar logic, we get the equations:
Since , we get 
.
So, the probability of reaching tails before heads is 
; we want the complement, 
, yielding an answer of 
.
Note: the same approach still works if we tried solving the original problem rather than the complement; we would have simply used 
and 
instead. The repeated back-substitution is cleaner because we used the complement.
See also
| 1995 AIME (Problems • Answer Key • Resources) | ||
| Preceded by Problem 14 |
Followed by Last question | |
| 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. 
