AMC 10 · 2012 · #24

Grade 8 countinglogic
Archetype Overlap / Complement Counting └ Sub-archetype Complement by Subtracting Forbidden Arrangements
combinations-basiccomplementary-counting casework ↑ Prerequisites: combinations-basic
📏 Medium solution 💡 3 insights
Problem
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.

Pick an answer.

(A)
108
(B)
132
(C)
671
(D)
846
(E)
1105

AMC 10 2012 problem © Mathematical Association of America (MAA AMC). Reproduced for educational use.

How to solve
Strategy Change Focus / Count the Complement

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.

1STEP 1

List each song's possible type

Label a song by the set of girls who like it. Banning the all-three set leaves 7 labels: none, three singles, three pairs.

7 types: ∅, {A},{B},{J}, {A,B},{B,J},{A,J}
2STEP 2

Restate the pair rule as coverage

A song liked by exactly Amy and Beth is just the pair label AB, so the rule becomes: all three pair labels must appear among the four songs.

3STEP 3

Count all label assignments first

Ignore the pair rule: each of the 4 songs takes any of the 7 labels independently, giving 2401 arrangements to trim.

7⁴ = 2401
4STEP 4

Subtract arrangements missing a pair

Banning one pair label leaves 6 choices per song, two leaves 5, all three leaves 4, so inclusion-exclusion removes the misses.

7⁴ - C(3, 1)6⁴ + C(3, 2)5⁴ - C(3, 3)4⁴
5STEP 5

Compute the final total

With 6⁴ = 1296, 5⁴ = 625, 4⁴ = 256: 2401 - 3888 + 1875 - 256 = 132, which is choice (B).

2401 - 3888 + 1875 - 256 = 132
Answer
132
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.
💡Key takeaway

When a problem demands 'at least one of each,' count every arrangement first and then subtract the ones that leave something out.

  • List each song's possible type
  • Restate the pair rule as coverage
  • Count all label assignments first
  • Subtract arrangements missing a pair
  • Compute the final total

More like this

Same archetype — closest grade level first.