Difference between revisions of "1995 AIME Problems/Problem 15"

Revision as of 22:26, 26 February 2018

Problem

Let $p_{}$ be the probability that, in the process of repeatedly flipping a fair coin, one will encounter a run of $5$ heads before one encounters a run of $2$ tails. Given that $p_{}$ can be written in the form $m/n$ where $m_{}$ and $n_{}$ are relatively prime positive integers, find $m+n$ .

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 $1$ to $4$ H's separated by T's and ending in $5$ 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 $3/2$ of it has to start with an H.

The answer to the problem is then the sum of all numbers of the form $\frac 32 \left( \frac 1{2^a} \cdot \frac 12 \cdot \frac 1{2^b} \cdot \frac 12 \cdot \frac 1{2^c} \cdots \right) \cdot \left(\frac 12\right)^5$ , where $a,b,c \ldots$ are all numbers $1-4$ , since the blocks of H's can range from $1-4$ in length. The sum of all numbers of the form $(1/2)^a$ is $1/2+1/4+1/8+1/16=15/16$ , 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 $\frac 32\left( \left(\frac {15}{16}\right)^n \cdot \left(\frac 12\right)^n \right) \cdot \left(\frac 1{32}\right)=\frac 3{64}\left(\frac{15}{32}\right)^n$ , where $n$ ranges from $0$ to $\infty$ , 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 $\frac{3/64}{1-(15/32)}=\frac{3}{34}$ , so the answer is $\boxed{037}$ .

Solution 2

Let $p_H, p_T$ respectively denote the probabilities that a string beginning with H's and T's are successful. Thus,

$p_T = \frac 12p_H.$

A successful string can either start with 1 to 4 H's, start with a T and then continue with a string starting with H (as there cannot be $2$ T's in a row, or be the string HHHHH.

There is a $\frac{15}{16}$ probability we roll $4$ consecutive H's, and there is a $\frac{15}{16}$ probability we roll a T. Thus,

$p_H = \left(\frac{15}{16}\right) \cdot \left(\frac 12\right) p_H + \frac{1}{32} \Longrightarrow p_H = \frac{1}{17}.$

The answer is $p_H + p_T = \frac{3}{2}p_H = \frac{3}{34}$ , and $m+n = \boxed{037}$ .

Solution 3

For simplicity, let's compute the complement, namely the probability of getting to $2$ tails before $5$ heads.

Let $h_{i}$ denote the probability that we get $2$ tails before $5$ heads, given that we have $i$ consecutive heads. Similarly, let $t_{i}$ denote the probability that we get $2$ tails before $5$ heads, given that we have $i$ consecutive tails. Specifically, $h_{5} = 0$ and $t_{2} = 1$ . If we can solve for $h_{1}$ and $t_{1}$ , we are done; the answer is simply $1/2 * (h_{1} + t_{1})$ , since on our first roll, we have equal chances of getting a string with "1 consecutive head" or "1 consecutive tail."

Consider solving for $t_{1}$ . 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:

$t_{1} = \frac{1}{2} t_{2} + \frac{1}{2} h_{1}$

Applying similar logic, we get the equations:

$\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*}$

Since $h_{5} = 0$ , we get $h_{4} = \frac{1}{2} t_{1}$ $\Rightarrow h_{3} = \frac{3}{4} t_{1}$ $\Rightarrow h_{2} = \frac{7}{8} t_{1}$ $\Rightarrow h_{1} = \frac{15}{16} t_{1}$ $\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}$ $\Rightarrow h_{1} = \frac{15}{16} \cdot \frac{16}{17} = \frac{15}{17}$ .

So, the probability of reaching $2$ tails before $5$ heads is $\frac{1}{2} (h_{1} + t_{1}) = \frac{31}{34}$ ; we want the complement, $\frac{3}{34}$ , yielding an answer of $3 + 34 = \boxed{037}$ .

Note: The same approach still works if we tried solving the original problem rather than the complement; we would have simply used $h_{5} = 1$ and $t_{2} = 0$ instead. The repeated back-substitution is cleaner because we used the complement.

@@ Line 10: / Line 10: @@
 === Solution 2 ===
-Let <math>p_H, p_T</math> respectively denote the probabilities that a string of <tt>H</tt>'s and <tt>T</tt>'s are successful. A successful string can either start with <tt>H</tt>, or it can start with <tt>T</tt> and then continue with a string starting with <tt>H</tt> (as there cannot be <math>2</math> <tt>T</tt>'s in a row). Thus
+Let <math>p_H, p_T</math> respectively denote the probabilities that a string beginning with <tt>H</tt>'s and <tt>T</tt>'s are successful. Thus,
+<center><math>p_T = \frac 12p_H.</math></center>
-<center><math>p_T = \frac 12p_H.</math></center>
+A successful string can either start with 1 to 4 H's, start with a T and then continue with a string starting with <tt>H</tt> (as there cannot be <math>2</math> <tt>T</tt>'s in a row, or be the string HHHHH.
-There is a <math>\frac{1}{16}</math> probability we roll <math>4</math> consecutive <tt>H</tt>'s, and there is a <math>\frac{15}{16}</math> probability we roll a <tt>T</tt>. Thus,
+There is a <math>\frac{15}{16}</math> probability we roll <math>4</math> consecutive <tt>H</tt>'s, and there is a <math>\frac{15}{16}</math> probability we roll a <tt>T</tt>. Thus,
 <center><math>p_H = \left(\frac{15}{16}\right) \cdot \left(\frac 12\right) p_H + \frac{1}{32} \Longrightarrow p_H = \frac{1}{17}.</math></center>

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

Page

Toolbox

Search