AMC 10 · 2012 · #24
Grade 8 countingAmy, 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 two girls but disliked by the third. In how many different ways is this possible?
Pick an answer.
AMC 10 2012 problem © Mathematical Association of America (MAA AMC). Reproduced for educational use.
Try it yourself first — the explanation is most useful after you’ve attempted it.
Toolkit + CCSS Solution
Understand
Restated: Amy, Beth, and Jo each like or dislike four different songs. No song may be liked by all three girls. For every one of the three possible pairs of girls, some song must be liked by exactly those two (and disliked by the third). Count how many like/dislike arrangements over the four songs meet both rules.
Givens: There are 4 different songs.; Each song can be liked by any subset of the three girls.; No song is liked by all three girls at once.; Each of the three pairs (Amy-Beth, Beth-Jo, Amy-Jo) must have at least one song liked by exactly those two.
Unknowns: The number of different like/dislike arrangements across all four songs that satisfy both rules.
Understand
Restated: Amy, Beth, and Jo each like or dislike four different songs. No song may be liked by all three girls. For every one of the three possible pairs of girls, some song must be liked by exactly those two (and disliked by the third). Count how many like/dislike arrangements over the four songs meet both rules.
Givens: There are 4 different songs.; Each song can be liked by any subset of the three girls.; No song is liked by all three girls at once.; Each of the three pairs (Amy-Beth, Beth-Jo, Amy-Jo) must have at least one song liked by exactly those two.
Plan
Primary tool: #16 Change Focus / Count the Complement
Secondary: #2 Make a Systematic List, #7 Identify Subproblems
The three pair conditions are all 'at least one' requirements, which are awkward to count head-on. First reframe each song by the set of girls who like it and list the allowed sets. Then, instead of building only the good arrangements, count them by complement: start from every arrangement and use inclusion-exclusion to subtract the ones that miss a required pair.
Execute — Answer: B
7.SP.C.8 Step 1 List each song's possible type
- Describe a song by the set of girls who like it.
- Since no song is liked by all three, the only allowed sets are the empty set, the three single-girl sets, and the three pair sets.
- That gives 7 possible types, and each of the 4 songs independently gets one of them.
💡 Naming a song by who likes it turns a fuzzy 'likes and dislikes' story into a clean choice of one label out of seven.
7.SP.C.8 Step 2 Restate the pair rule as coverage
- A song liked by exactly Amy and Beth is precisely a song of type {A,B}, and likewise for the other pairs.
- So the rule 'each pair has such a song' means that among the four song-labels, each of the three pair-types {A,B}, {B,J}, {A,J} must appear at least once.
- The single-girl and empty types are unrestricted.
💡 The three separate 'at least one' demands collapse into one picture: all three pair-labels must show up.
8.EE.A.1 Step 3 Count all label assignments first
- Ignore the pair rule for a moment.
- Each of the 4 songs can be any of the 7 types, and the choices are independent, so there are 7 x 7 x 7 x 7 arrangements in all.
- This is the pool we will trim.
💡 Counting everything first and then removing the bad cases is easier than building only the good cases directly.
7.SP.C.8 Step 4 Subtract arrangements missing a pair
- Let bad event M1 be 'type {A,B} never appears,' and M2, M3 the same for {B,J} and {A,J}.
- If one pair-type is banned, each song has 6 remaining choices, so each single bad event has 6^4 arrangements.
- Banning two pair-types leaves 5 choices per song, giving 5^4 for each pair of bad events.
- Banning all three leaves 4 choices, giving 4^4.
- By inclusion-exclusion, the arrangements that satisfy all three pair rules equal the total minus the union of the bad events.
💡 Cases missing two pairs get subtracted twice, so inclusion-exclusion adds the overlaps back to keep the count honest.
7.NS.A.3 Step 5 Compute the final total
- Evaluate the powers: 6^4 = 1296, 5^4 = 625, and 4^4 = 256.
- Then 2401 - 3(1296) + 3(625) - 256 = 2401 - 3888 + 1875 - 256 = 132.
- So there are 132 valid arrangements, which is answer (B).
💡 Plugging the powers into the inclusion-exclusion formula collapses everything into the single count of good arrangements.
7.SP.C.8 Describe a song by the set of girls who like it. Since no song is liked by all t 7.SP.C.8 A song liked by exactly Amy and Beth is precisely a song of type {A,B}, and like 8.EE.A.1 Ignore the pair rule for a moment. Each of the 4 songs can be any of the 7 types 7.SP.C.8 Let bad event M1 be 'type {A,B} never appears,' and M2, M3 the same for {B,J} an 7.NS.A.3 Evaluate the powers: 6^4 = 1296, 5^4 = 625, and 4^4 = 256. Then 2401 - 3(1296) + Review
Reasonableness: 132 is far smaller than the 2401 unrestricted arrangements, which fits: forcing all three pair-types to appear is a strong restriction. It also comfortably exceeds the 24 ways of merely seating the three pair-types on three songs, since the fourth song adds several options. Among the choices only (B) 132 lands in this range; the large options 671, 846, and 1105 would require almost no restriction at all.
Alternative: Count directly by casework on the fourth song. First place the three required pair-types on three of the four songs: there are 4 x 3 x 2 = 24 ordered ways. If the fourth song is a non-pair type (empty, {A}, {B}, or {J} - 4 options) nothing is duplicated, giving 24 x 4 = 96. If the fourth song repeats one of the three pair-types (3 options), two songs share a pair-type and are interchangeable, so divide by 2: 24 x 3 / 2 = 36. The total is 96 + 36 = 132, matching the complement count.
CCSS standards used (min grade 8)
7.SP.C.8Probabilities of compound events using organized lists (Modeling each song as one of 7 like-sets and organizing the outcome count, including the inclusion-exclusion setup)8.EE.A.1Properties of integer exponents (Evaluating the powers 7^4, 6^4, 5^4, and 4^4 that count independent song choices)7.NS.A.3Four operations with rational numbers (Combining the inclusion-exclusion terms into the final total of 132)
⭐ When a problem demands 'at least one of each,' count every arrangement first and then subtract the ones that leave something out.
⭐ When a problem demands 'at least one of each,' count every arrangement first and then subtract the ones that leave something out.
More like this
Same archetype — closest grade level first.
