1990 AIME Problem 9

Question

A fair coin is to be tossed

10

times. Let

\frac{i}{j},

in lowest terms, be the probability that heads never occur on consecutive tosses. Find

i+j.

Answer

Count valid length-

n

toss strings according to whether they end in tails or heads

The resulting recurrence is Fibonacci-like, with initial counts

2

and

3

Let

u_n

be the number of length-

n

toss strings with no consecutive heads. A valid string ending in tails is obtained by appending

\mathrm{T}

to any valid length-

(n-1)

string, while one ending in heads is obtained by appending

\mathrm{TH}

to any valid length-

(n-2)

string. Hence

u_n=u_{n-1}+u_{n-2},

with

u_1=2

and

u_2=3.

This gives

u_{10}=144.

The probability is

\frac{144}{2^{10}}=\frac{9}{64},

so

i+j=9+64=73.

Problem 9 in other years