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 five HH, three HT, two TH, and four 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 comb(r+n-1,r) and multiplication, the answer is {{5+4-1}\choose5}

See also

• 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.