Maths Olympiad Prep

Library / /313 of 520

Combinatorics Difficulty 5.4 AIME, harder Find the answer

Example 5 In coin tossing, if Z represents heads and F represents tails, then the sequence of coin tosses is represented by a string composed of Z and F. We can count the number of occurrences of heads followed by tails (ZF), heads followed by heads (ZZ)...... For example, the sequence ZZFFZZZZFZZFFFF is the result of 15 coin tosses, which includes 5 ZZ, 3 ZF, 2 FZ, and 4 FF. How many sequences of 15 coin tosses have exactly 2 ZZ, 3 ZF, 4 FZ, and 5 FF?
(4th American Invitational Mathematics Examination (AIME))

A number or a short expression. Spacing and $ signs are ignored.

Solution

Solution: The sequences that meet the requirements have the following two possible forms:
(1) Starting with F: FFZZFFZZF \cdots F Z \cdots Z F \cdots F Z \cdots Z;
(2) Starting with Z: ZZFFZZFF\mathrm{Z} \cdots \mathrm{ZF} \cdots \mathrm{FZ} \cdots \mathrm{ZF} \cdots \mathrm{F}.
Since the sequence is required to have exactly 3 ZF\mathrm{ZF}, if the sequence belongs to (2), it should have the form
 Z ZFFZZFFZZFF \text { Z } \cdots \underline{Z F} \cdots F Z \cdots Z F \cdots F Z \cdots Z F \cdots F \text {. }

which contains only 2 FZ\mathrm{FZ}, failing to meet the requirement of 4 FZ\mathrm{FZ}. Therefore, the sequence that meets the requirements can only be of form (1).

Since the sequence has exactly 4 FZ\mathrm{FZ}, when considering the sequence with exactly two ZZ, it can be divided into the following two categories: \qquad ZZZ \qquad
\qquad
\qquad Z, \qquad ZZ \qquad ZZ \qquad Z \qquad Z
and the different positions of Z\mathrm{Z}, with the spaces filled with F\mathrm{F}.
Let the number of F\mathrm{F} in each space be x1x_{1}, x2x_{2}, x3x_{3}, x4x_{4}, then x1+x2+x3+x4=9x_{1}+x_{2}+x_{3}+x_{4}=9 has C83=56\mathrm{C}_{8}^{3}=56 positive integer solutions.

On the other hand, for (1), the position of ZZZ has 4 possibilities, and for (2), the arrangement of ZZ,ZZ,Z,Z\mathrm{ZZ}, \mathrm{ZZ}, \mathrm{Z}, \mathrm{Z} has 6 possibilities, so the arrangement of Z\mathrm{Z} has 10 possibilities.
Therefore, the number of sequences that meet the requirements is
10×56=560 (sequences)  10 \times 56=560 \text { (sequences) }

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.