AIME 1986 · 第 13 题

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 ${{5+3}\choose3} = 56$ combinations. We do the same with 2 Hs to get ${{2+3}\choose3} = 10$ combinations; thus there are $56 \cdot 10 = \boxed {560}$ 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 $\dbinom{r+n-1}{r}$ and multiplication, the answer is ${{2+4-1}\choose2} \cdot{{5+4-1}\choose5}=560$ ~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 $2$ more H's and $5$ more T's. Since we have a total of $7$ additional flips left, we will have exactly $2$ more H's and $5$ 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

$${8 \choose 3}{5 \choose 2}=(56)(10)=560$$ ways do distribute the T's and H's. Hence, there are $\boxed {560}$ different sequences.

• [We want to divide $5$ 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 $1+4=5$ 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 $5$ TT sequences if we divide the additional T's among the first $4$ 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