Difference between revisions of "1995 AIME Problems/Problem 15"
(→Solution 5) |
|||
(33 intermediate revisions by 20 users not shown) | |||
Line 1: | Line 1: | ||
== Problem == | == Problem == | ||
+ | Let <math>p_{}</math> be the [[probability]] that, in the process of repeatedly flipping a fair coin, one will encounter a run of <math>5</math> heads before one encounters a run of <math>2</math> tails. Given that <math>p_{}</math> can be written in the form <math>m/n</math> where <math>m_{}</math> and <math>n_{}</math> are relatively prime positive integers, find <math>m+n</math>. | ||
+ | __TOC__ | ||
== Solution == | == Solution == | ||
+ | === 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>. | ||
+ | |||
+ | 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>. | ||
+ | |||
+ | === Solution 2 === | ||
+ | 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> | ||
+ | |||
+ | 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} \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> | ||
+ | |||
+ | 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} \cdot \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{037}</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. | ||
+ | |||
+ | ==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 <math>\frac{1}{32},\frac{1}{64},\frac{1}{4},\frac{1}{8},\frac{1}{16},\frac{1}{32},\frac{1}{64}</math> respectively. The ones where there is five heads are AAAAA and BAAAAA. The sum of these probabilities are <math> \frac{3}{64}</math>. The sum of all these endgame outcomes are <math>\frac{34}{64}</math>, hence the desired probability is <math>\frac{3}{34}</math>, and in this case <math>m=3,n=34</math> so we have <math>m+n=\boxed{037}</math> | ||
+ | -vsamc | ||
+ | |||
+ | ==Solution 5== | ||
+ | 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 | ||
+ | |||
+ | ==Video solution== | ||
+ | |||
+ | https://www.youtube.com/watch?v=Vo-4w5Cor9w&t | ||
== See also == | == See also == | ||
− | + | {{AIME box|year=1995|num-b=14|after=Last question}} | |
+ | |||
+ | [[Category:Intermediate Combinatorics Problems]] | ||
+ | {{MAA Notice}} |
Latest revision as of 13:05, 14 October 2024
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 .
Contents
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 has to start with an 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 beginning with H's and T's are successful. Thus,
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 T's in a row, or be the string HHHHH.
There is a probability we roll HHHH and then T. On the other hand, there is a probability we roll a H, HH, HHH, or HHHH, and then a T. 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.
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 respectively. The ones where there is five heads are AAAAA and BAAAAA. The sum of these probabilities are . The sum of all these endgame outcomes are , hence the desired probability is , and in this case so we have -vsamc
Solution 5
There can be 1-4 heads and 1 tails in any grouping, so we write etc., where and subscript means there are of that state in a row. We see that this gives us 2 geometric sequences: one with first term and common ratio and one with first tem and the same common ratio. Therefore we get or ~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.