1986 AIME Problem 13

Attempt Problem 13 of the 1986 AIME below, then check your answer against the professionally curated solution from LIVE by Po-Shen Loh. You can also try the full timed exam, view all 1986 AIME solutions, or check the answer key.

All problems are used with official legal permission of the Mathematical Association of America (MAA).

13.

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 TH,\mathrm{TH}, HH,\mathrm{HH}, and so on. For example, in the sequence HHTTHHHHTHHTTTT\mathrm{HHTTHHHHTHHTTTT} of 1515 coin tosses, there are two HH,\mathrm{HH}, three HT,\mathrm{HT}, four TH,\mathrm{TH}, and five TT\mathrm{TT} subsequences. How many different sequences of 1515 coin tosses contain exactly two HH,\mathrm{HH}, three HT,\mathrm{HT}, four TH,\mathrm{TH}, and five TT\mathrm{TT} subsequences?

Answer: 560
Concepts:arrangements with restrictionsmultiplication principlestars and bars
Difficulty rating: 2350
Small Hint:

Compare the numbers of HT\mathrm{HT} and TH\mathrm{TH} transitions to determine the first and last tosses

Big Hint:

Translate the HH\mathrm{HH} and TT\mathrm{TT} counts into totals distributed among alternating runs

Solution:

Since there are four TH\mathrm{TH} transitions and three HT\mathrm{HT} transitions, every valid sequence starts with T\mathrm{T} and ends with H.\mathrm{H}. It therefore has four T\mathrm{T}-runs and four H\mathrm{H}-runs, alternating.

If the H\mathrm{H}-runs have total length h,h, then the number of HH\mathrm{HH} transitions is h4.h-4. Thus h=6,h=6, and the positive lengths of the four H\mathrm{H}-runs can be chosen in (6141)=(53)=10\binom{6-1}{4-1}=\binom53=10 ways. Similarly, five TT\mathrm{TT} transitions mean that the four T\mathrm{T}-runs have total length 9,9, giving (9141)=(83)=56\binom{9-1}{4-1}=\binom83=56 choices. The alternating order is fixed, so the number of sequences is 1056=560.10\cdot56=560.

← Problem 12#12
Full Exam

Problem 13 in Other Years