1995 AIME Problems/Problem 15
Problem
Let 
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 can be written in the form 
where 
and 
are relatively prime positive integers, find 
.
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 
, 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 
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 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 
, so the answer is 37.
