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 heads before one encounters a run of tails. Given that can be written in the form where and are relatively prime positive integers, find .

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 had to start with and 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 of H's and T's are successful. A successful string can either start with H, or it can start with T and then continue with a string starting with H (as there cannot be T's in a row). Thus

A successful string starting with H must start with a block of H's, then a T, then a successful string starting with H, or reach a block of H's. Thus,

The answer is , and .