2012 AMC 10B Problem 24

P21-25~6 minPrint

Basic Counting Inclusion-Exclusion Map the objects to something easier to count Split into exhaustive cases and handle each

Amy, Beth, and Jo listen to four different songs and discuss which ones they like. No song is liked by all three. Furthermore, for each of the three pairs of the girls, there is at least one song liked by those girls but disliked by the third. In how many different ways is this possible?

Show solution without answering

Key insight

Give each song a label: the group of girls who like it. There are 7 allowed labels, and the three two-girl labels must each be used at least once.

Solution

1. Turn it into labels. For each song, write down which girls like it. With Amy ( $A$ ), Beth ( $B$ ) and Jo ( $J$ ), a song can be liked by:
- nobody;
- one girl: $A$ , $B$ or $J$ ;
- two girls: $AB$ , $AJ$ or $BJ$ ;
- all three: $ABJ$ , which is not allowed.
That leaves $7$ labels.
2. The second rule. "Some song is liked by Amy and Beth but not Jo" means the label $AB$ is used on at least one song. The same goes for $AJ$ and $BJ$ . So all three two-girl labels must appear among the four songs.
3. Three labels must fit on four songs, so there are only two ways it can go. Either each two-girl label is used once and the fourth song gets something else, or one two-girl label is used twice.

Case 1: each two-girl label once, plus one other song.

Choose which song is the "other" one: $4$ ways.
Give it a label that is not a two-girl label: nobody, $A$ , $B$ or $J$ , so $4$ ways.
Put $AB$ , $AJ$ , $BJ$ on the remaining three songs in some order: $3 \times 2 \times 1 = 6$ ways.
Case 1 total: $4 \times 4 \times 6 = 96$ .

Case 2: one two-girl label used twice.

Choose which label is doubled: $3$ ways.
Choose the two songs that get it: from $4$ songs that is $6$ ways ( $12, 13, 14, 23, 24, 34$ ).
Put the other two labels on the last two songs: $2$ ways.
Case 2 total: $3 \times 6 \times 2 = 36$ .

Adding the cases: $96 + 36 = 132$ .

The answer is $\boxed{\textbf{(B)}\ 132}$ .

Why this works

Labeling each song by who likes it turns a wordy situation into "put one of $7$ labels on each of $4$ songs, making sure three particular labels appear." When required items must be placed and there are a few extra spots, split into cases by how many times each required item is used. That keeps you from counting the same arrangement twice, which is what happens if you let the fourth song take a two-girl label in Case 1.

Alternative approach

Count everything, then remove the bad ones. Without the second rule there are $7^4 = 2401$ ways. Ways that never use $AB$ : $6^4 = 1296$ , and the same for $AJ$ and $BJ$ . Taking away $3 \times 1296$ removes the ways missing two labels twice, so add those back: $3 \times 5^4 = 1875$ . Ways missing all three labels were removed three times and added back three times, so take them away once more: $4^4 = 256$ .
$2401 - 3888 + 1875 - 256 = 132.$

Concise solution

A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.

Describe each song by the set of girls who like it. The set $\{A, B, J\}$ is forbidden, leaving $7$ possible labels: the empty set, three singletons, and the three pairs $AB$ , $AJ$ , $BJ$ . The second condition says each of the three pair-labels is used by at least one of the four songs. Since there are four songs and three required labels, split by how the pair-labels are distributed.

Case 1: each pair-label used once, plus one other song. Choose which song is the extra one ( $4$ ways), assign the three pair-labels to the other three songs ( $3! = 6$ ways), and give the extra song one of the $4$ non-pair labels (empty or a singleton): $4 \cdot 6 \cdot 4 = 96$ .

Case 2: one pair-label used twice, the other two once. Choose the repeated label ( $3$ ways), choose which two songs carry it ( $\binom42 = 6$ ), and assign the other two labels to the remaining two songs ( $2$ ways): $3 \cdot 6 \cdot 2 = 36$ .

Total: $96 + 36 = 132$ .

The answer is $\boxed{\textbf{(B)}\ 132}$ .

Review in the AoPS books

Introduction to Counting & Probability, Chapter 1: Counting Is Arithmetic
Introduction to Counting & Probability, Chapter 2: Basic Counting Techniques (§2.2)
Intermediate Counting & Probability, Chapter 4: Constructive Counting and 1-1 Correspondences (§4.4, §4.5, §4.6)
Intermediate Counting & Probability, Chapter 3: A Piece of PIE (§3.2, §3.3)