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 "1995 AIME Problems/Problem 15"

(→‎solution 5 (has lots of variables and steps, but it is very easy to think up))
m (→‎Solution 1)
 
(8 intermediate revisions by 5 users not shown)
Line 5: Line 5:
 
== Solution ==
 
== Solution ==
 
=== Solution 1 ===
 
=== Solution 1 ===
−
Think of the problem as a sequence of <tt>H</tt>'s and <tt>T</tt>'s. No two <tt>T</tt>'s can occur in a row, so the sequence is blocks of <math>1</math> to <math>4</math> <tt>H</tt>'s separated by <tt>T</tt>'s and ending in <math>5</math> <tt>H</tt>'s. Since the first letter could be <tt>T</tt> or the sequence could start with a block of <tt>H</tt>'s, the total probability is that <math>3/2</math> of it has to start with an <tt>H</tt>.  
+
Think of the problem as a sequence of <tt>H</tt>'s and <tt>T</tt>'s. No two <tt>T</tt>'s can occur in a row, so the successful sequences are composed of blocks of <math>1</math> to <math>4</math> <tt>H</tt>'s separated by <tt>T</tt>'s and end with <math>5</math> <tt>H</tt>'s. Since the probability that the sequence starts with <tt>TH</tt> is <math>1/4</math>, the total probability is that <math>3/2</math> of the probability given that the sequence starts with an <tt>H</tt>.  
  
 
The answer to the problem is then the sum of all numbers of the form <math>\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</math>, where <math>a,b,c \ldots </math> are all numbers <math>1-4</math>, since the blocks of <tt>H</tt>'s can range from <math>1-4</math> in length. The sum of all numbers of the form <math>(1/2)^a</math> is <math>1/2+1/4+1/8+1/16=15/16</math>, so if there are n blocks of <tt>H</tt>'s before the final five <tt>H</tt>'s, the answer can be rewritten as the sum of all numbers of the form <math>\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</math>, where <math>n</math> ranges from <math>0</math> to <math>\infty</math>, since that's how many blocks of <tt>H</tt>'s there can be before the final five. This is an infinite geometric series whose sum is <math>\frac{3/64}{1-(15/32)}=\frac{3}{34}</math>, so the answer is <math>\boxed{037}</math>.
 
The answer to the problem is then the sum of all numbers of the form <math>\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</math>, where <math>a,b,c \ldots </math> are all numbers <math>1-4</math>, since the blocks of <tt>H</tt>'s can range from <math>1-4</math> in length. The sum of all numbers of the form <math>(1/2)^a</math> is <math>1/2+1/4+1/8+1/16=15/16</math>, so if there are n blocks of <tt>H</tt>'s before the final five <tt>H</tt>'s, the answer can be rewritten as the sum of all numbers of the form <math>\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</math>, where <math>n</math> ranges from <math>0</math> to <math>\infty</math>, since that's how many blocks of <tt>H</tt>'s there can be before the final five. This is an infinite geometric series whose sum is <math>\frac{3/64}{1-(15/32)}=\frac{3}{34}</math>, so the answer is <math>\boxed{037}</math>.
Line 15: Line 15:
 
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.
 
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{1}{16} \cdot \frac{1}{2} = \frac{1}{32}</math> probability we roll <tt>HHHH</tt> and then <tt>T</tt>. On the other hand, there is a <math>\frac{15}{16}</math> probability we roll a <tt>H, HH, HHH, or HHHH</tt>, and then 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>
 
<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>
Line 51: Line 51:
 
-vsamc
 
-vsamc
  
−
 
+
==Solution 5==
−
==Solution 5 (has lots of variables and steps, but it is very easy to think up) ==
+
There can be 1-4 heads and 1 tails in any grouping, so we write <math>h_5,th_5,h_nth_5,th_nth_5,…</math> etc., where <math>1\leq n\leq 4</math> and subscript <math>n</math> means there are <math>n</math> of that state in a row. We see that this gives us 2 geometric sequences: one with first term <math>\frac{1}{2^5}</math> and common ratio <math>\frac{1}{2}*\left(1/2+1/4+1/8+1/16\right)</math> and one with first tem <math>\frac{1}{2^6}</math> and the same common ratio. Therefore we get <math>\frac{3}{34}</math> or <math>\fbox{037}</math>
−
 
+
~joeythetoey
−
Front note: The states are
 
−
(h=heads t=tails)
 
−
 
 
−
<math>h_1</math> is the probability of having exactly 1 H in a row.
 
−
<math>h_2</math> is the probability of having exactly 2 Hs in a row.
 
−
<math>h_3</math> is the probability of having exactly 3 Hs in a row.
 
−
<math>h_4</math> is the probability of having exactly 4 Hs in a row.
 
−
<math>h_5</math> is the probability of having exactly 5 Hs in a row.
 
−
<math>t_1</math> is the probability of having exactly 1 T in a row.
 
−
<math>t_2</math> is the probability of having exactly 2 Ts in a row.
 
−
 
 
−
 
 
−
(1)Since the probability to get one H is <math>\frac{1}{2}</math>, thus the probability of getting two H's in a row is <math>\frac{1}{2} \cdot \frac{1}{2}</math>. Hence we have <math>h_2 = \frac{h_1}{2}</math>. Similarly, <math>h_3 = \frac{h_1}{4}</math>, <math>h_4 = \frac{h_1}{8}</math> and <math>h_5 = \frac{h_1}{16}</math>
 
−
 
 
−
(2)We can also see  <math>h_1 = \frac{1}{2} + \frac{t_1}{2}</math> because the first move has probability <math>\frac{1}{2}</math> of landing heads, and any time there is tails, there is a <math>\frac{1}{2}</math> chance of getting a head.
 
−
 
 
−
(3)Similar to part (1), <math>t_2 = \frac{t_1}{2}</math>
 
−
 
 
−
(4)We also have <math>t_1 = \frac{1}{2} + \frac{h_1}{2} +\frac{h_2}{2} +\frac{h_3}{2} + \frac{h_4}{2}</math> and by then by using (1),  <math>t_1 = \frac{1}{2} + \frac{15h_1}{16}</math>
 
−
 
 
−
(5)Using (2) and (4) we can solve for <math>t_1</math> and <math>h_1</math>. We get <math>h_1 = \frac{24}{17}</math>, and <math>t_1 = \frac{31}{17}</math>.
 
−
 
 
−
Since <math>h_5 = \frac{h_1}{16}</math>, we now know  <math>h_5 = \frac{3}{34}</math>, and since <math>t_2 = \frac{t_1}{2}</math>, <math>t_2 = \frac{31}{34}</math>.
 
−
 
 
−
We are looking for <math>\frac{h_5}{h_5+t_2}</math>, which gives the answer <math>\frac{3}{34}</math>. Hence <math>m+n=\boxed{37}</math>.
 
−
 
 
−
 
 
−
 
 
−
intelligence_20
 
  
 
==Video solution==
 
==Video solution==

Latest revision as of 12:09, 17 November 2024

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 successful sequences are composed of blocks of $1$ to $4$ H's separated by T's and end with $5$ H's. Since the probability that the sequence starts with TH is $1/4$, the total probability is that $3/2$ of the probability given that the sequence starts 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{1}{16} \cdot \frac{1}{2} = \frac{1}{32}$ probability we roll HHHH and then T. On the other hand, there is a $\frac{15}{16}$ probability we roll a H, HH, HHH, or HHHH, and then 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.

Solution 4(fast)

Consider what happens in the "endgame" or what ultimately leads to the end. Let A denote that a head has been flipped, and let B denote that a tail has been flipped. The endgame outcomes are AAAAA, BAAAAA, BB, ABB, AABB, AAABB, AAAABB. The probabilities of each of these are $\frac{1}{32},\frac{1}{64},\frac{1}{4},\frac{1}{8},\frac{1}{16},\frac{1}{32},\frac{1}{64}$ respectively. The ones where there is five heads are AAAAA and BAAAAA. The sum of these probabilities are $\frac{3}{64}$. The sum of all these endgame outcomes are $\frac{34}{64}$, hence the desired probability is $\frac{3}{34}$, and in this case $m=3,n=34$ so we have $m+n=\boxed{037}$ -vsamc

Solution 5

There can be 1-4 heads and 1 tails in any grouping, so we write $h_5,th_5,h_nth_5,th_nth_5,…$ etc., where $1\leq n\leq 4$ and subscript $n$ means there are $n$ of that state in a row. We see that this gives us 2 geometric sequences: one with first term $\frac{1}{2^5}$ and common ratio $\frac{1}{2}*\left(1/2+1/4+1/8+1/16\right)$ and one with first tem $\frac{1}{2^6}$ and the same common ratio. Therefore we get $\frac{3}{34}$ or $\fbox{037}$ ~joeythetoey

Video solution

https://www.youtube.com/watch?v=Vo-4w5Cor9w&t

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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1995_AIME_Problems/Problem_15&oldid=234658"