1986 AIME Problem 13

Question

In a sequence of coin tosses, one can keep a record of instances in which a tail is immediately followed by a head, a head is immediately followed by a head, and so on. We denote these by

\mathrm{TH},

\mathrm{HH},

and so on. For example, in the sequence

\mathrm{HHTTHHHHTHHTTTT}

of

15

coin tosses, there are two

\mathrm{HH},

three

\mathrm{HT},

four

\mathrm{TH},

and five

\mathrm{TT}

subsequences. How many different sequences of

15

coin tosses contain exactly two

\mathrm{HH},

three

\mathrm{HT},

four

\mathrm{TH},

and five

\mathrm{TT}

subsequences?

Answer

Answer: 560

Concepts:arrangements with restrictions multiplication principle stars and bars

Difficulty rating: 2350

Small hint:

Compare the numbers of

\mathrm{HT}

and

\mathrm{TH}

transitions to determine the first and last tosses

Big hint:

Translate the

\mathrm{HH}

and

\mathrm{TT}

counts into totals distributed among alternating runs

Solution:

Since there are four

\mathrm{TH}

transitions and three

\mathrm{HT}

transitions, every valid sequence starts with

\mathrm{T}

and ends with

\mathrm{H}.

It therefore has four

\mathrm{T}

-runs and four

\mathrm{H}

-runs, alternating.

If the

\mathrm{H}

-runs have total length

h,

then the number of

\mathrm{HH}

transitions is

h-4.

Thus

h=6,

and the positive lengths of the four

\mathrm{H}

-runs can be chosen in

\binom{6-1}{4-1}=\binom53=10

ways. Similarly, five

\mathrm{TT}

transitions mean that the four

\mathrm{T}