1986 AIME Problems/Problem 13
Problem
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 etc. We denote these by TH, HH, and etc. For example, in the sequence TTTHHTHTTTHHTTH of 15 coin tosses we observe that there are two HH, three HT, four TH, and five TT subsequences. How many different sequences of 15 coin tosses will contain exactly two HH, three HT, four TH, and five TT subsequences?
Solution
Let's consider each of the sequences of two coin tosses as an operation instead; this operation takes a string and adds the next coin toss on (eg, THHTH + HT = THHTHT). We examine what happens to the last coin toss. Adding HH or TT is simply an identity for the last coin toss, so we will ignore them for now. However, adding HT or TH switches the last coin. H switches to T three times, but T switches to H four times; hence it follows that our string will have a structure of THTHTHTH.
Now we have to count all of the different ways we can add the identities back in. There are 5 TT subsequences, which means that we have to add 5 T into the strings, as long as the new Ts are adjacent to existing Ts. There are already 4 Ts in the sequence, and since order doesn’t matter between different tail flips this just becomes the ball-and-urn argument. We want to add 5 balls into 4 urns, which is the same as 3 dividers; hence this gives 
combinations. We do the same with 2 Hs to get 
combinations; thus there are 
possible sequences.
SLIGHT VARIATION ON FINAL ARGUMENT
The structure of the final order is T_H_T_H_T_H_T_H_, and there are 4 spots to put the 2 heads in, and 4 spots to put the 5 tails in. By using the formula for distributing r identical objects into n distinct boxes 
and multiplication, the answer is 
* 
=560
See also
| 1986 AIME (Problems • Answer Key • Resources) | ||
| Preceded by Problem 12 |
Followed by Problem 14 | |
| 1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
| All AIME Problems and Solutions | ||
- AIME Problems and Solutions
- American Invitational Mathematics Examination
- Mathematics competition resources
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. 
