1995 AIME Problems/Problem 15

Revision as of 19:21, 2 April 2008 by Dgreenb801 (talk | contribs) (Solution)

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)\cdot(1/32)=3/64(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/64)/(1-(15/32))=3/34$, so the answer is 37.

See also