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

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 ~Slight edits in LaTeX by EthanSpoon

Solution 2

We need exactly four TH subsequences, so we can place additional T's and H's between four blocks of TH:

_TH_TH_TH_TH_

Since we cannot put additional TH sequences between the four blocks, each of the three spaces in between them will contain a HT subsequence. So now we just need two HH sequences and five TT sequences.

For these criteria to be satisfied, we need at least more H's and more T's. Since we have a total of additional flips left, we will have exactly more H's and more T's. For reasons explained below, the T's can be distributed to the first four spaces and the H's can be distributed to the last 4* (since we cannot have anymore TH sequences, the T's are always to the right of the H's). By stars and bars, there are ways do distribute the T's and H's. Hence, there are different sequences.

• [We want to divide T's among the spaces to form exactly five TT subsequences. Each time we divide the group of T's (TTTTT) to make an additional group, we lose one TT sequence. However, each of the first 4 spaces are adjacent to one T. So each time we divide the T's, if we place the group in one of the first four spaces, we gain back another TT sequence. We start with one group that has four TT sequences, so when we place them in the spaces, we get TT sequences. Since the number of TT sequences stays the same each time we divide the T's into smaller groups, we will always have TT sequences if we divide the additional T's among the first spaces. We can use identical logic to show why we can divide the two H's among the last four spaces to get exactly two HH subsequences.]

~ azc1027

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.