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

m
(Solution)
Line 3: Line 3:
  
 
== Solution ==
 
== Solution ==
 +
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 3/2 that of it had to start with and H. The answer to the problem is then the sum of all numbers of the form <math>3/2((1/2)^a\cdot1/2\cdot(1/2)^b\cdot1/2\cdot(1/2)^c...)\cdot(1/2)^5)</math>, where a,b,c... 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 <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 H's before the final five H's, the answer can be rewritten as the sum of all numbers of the form <math>3/2((15/16)^n\cdot(1/2)^n)=3/2(15/32)^n</math>, where n ranges from 0 to infinity, 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 <math>(3/2)/(1-(15/32))=3/34</math>, so the answer is 37.
  
 
== See also ==
 
== See also ==
 
* [[1995_AIME_Problems/Problem_14|Previous Problem]]
 
* [[1995_AIME_Problems/Problem_14|Previous Problem]]
 
* [[1995 AIME Problems]]
 
* [[1995 AIME Problems]]

Revision as of 20:18, 2 April 2008

Problem

Let $\displaystyle 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 $\displaystyle p_{}$ can be written in the form $\displaystyle m/n$ where $\displaystyle m_{}$ and $\displaystyle n_{}$ are relatively prime positive integers, find $\displaystyle m+n$.

Solution

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 3/2 that of it had to start with and H. The answer to the problem is then the sum of all numbers of the form $3/2((1/2)^a\cdot1/2\cdot(1/2)^b\cdot1/2\cdot(1/2)^c...)\cdot(1/2)^5)$, where a,b,c... 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 $3/2((15/16)^n\cdot(1/2)^n)=3/2(15/32)^n$, where n ranges from 0 to infinity, 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 $(3/2)/(1-(15/32))=3/34$, so the answer is 37.

See also