AMC 10 · 2021 · #15

Grade 11 counting

Archetype Casework by Position / Vertex Type └ Sub-archetype Count of Type

combinations-basiccombinatorial-identitycomplementary-countingmodular-arithmetic identify-subproblemssystematic-enumeration ↑ Prerequisites: combinations-basic

📏 Long solution 💡 3 insights

Problem

A choir director builds a group out of 6 tenors and 8 basses. A group is allowed when the number of tenors and the number of basses differ by a multiple of 4, and the group is not empty. Find the remainder when the number of allowed groups is divided by 100.

Pick an answer.

(A)

(B)

(C)

(D)

(E)

How to solve

Strategy Change Focus / Count the Complement

Written directly, N is a sum of about fifteen products C(6, t)C(8, b), one for each allowed pair. That is finishable but slow, and it hides why the answer comes out clean. The trouble is the minus sign: the two groups are being compared by subtraction, so they refuse to merge. The fix is to count the basses you leave out instead of the basses you take. That swap costs nothing, because choosing which basses to include and choosing which basses to exclude are the same decision, and it turns the difference into a sum. Once the rule reads "the two counts add to a multiple of 4," the tenors and the basses are being asked the same question, so the whole problem collapses into one question about a single pool of 14 people. From there it is four binomial coefficients, one subtraction for the empty group, and one division.

1STEP 1

Name the two counts

The condition is about a difference.

C(6, t)C(8, b), 0 ≤ t ≤ 6, 0 ≤ b ≤ 8, 4 ∣ (t - b)

2STEP 2

Count the basses left out

Counting the left-out basses turns the difference into a sum.

u = 8 - b, C(8, b) = C(8, u), t - b = t + u - 8 ⟹ 4 ∣ (t - b) ⇔ 4 ∣ (t + u)

3STEP 3

Merge into one pool of fourteen

The two groups merge into one pool.

S = T ∪ U, |T| = t, |U| = u, |S| = t + u, #{S : |S| = s} = C(14, s)

4STEP 4

List the surviving sizes

Only sizes divisible by four survive.

0 ≤ |S| ≤ 14, |S| ∈ {0, 4, 8, 12}

5STEP 5

Add the binomial coefficients

The four coefficients add to a power of two.

C(14, 0) + C(14, 4) + C(14, 8) + C(14, 12) = 1 + 1001 + 3003 + 91 = 4096 = 2¹²

6STEP 6

Drop the empty group and divide

Removing the empty group and dividing gives 95.

N = 4096 - 1 = 4095, 4095 = 40 · 100 + 95

Answer

Two independent checks. First, scale: ignoring the rule entirely there are 2¹⁴ - 1 = 16383 non-empty groups, and a rule that keeps one of the four possible remainders should keep roughly a quarter of them. Since 16383/4 ≈ 4096, the value N = 4095 sits exactly where it should. Second, redo the count in the original variables and see whether the same numbers appear. The allowed differences are t - b = -8, -4, 0, 4. For t - b = -8 the only pair is (0,8), giving 1 · 1 = 1. For t - b = -4 the pairs are (0,4), (1,5), (2,6), (3,7), (4,8), giving 1 · 70 + 6 · 56 + 15 · 28 + 20 · 8 + 15 · 1 = 1001. For t - b = 0 the pairs run (0,0) through (6,6), giving 1 · 1 + 6 · 8 + 15 · 28 + 20 · 56 + 15 · 70 + 6 · 56 + 1 · 28 = 3003. For t - b = 4 the pairs are (4,0), (5,1), (6,2), giving 15 · 1 + 6 · 8 + 1 · 28 = 91. These four case totals are the same four binomial coefficients 1, 1001, 3003, 91 found by the merged method, and they add to 4096. Removing the empty group again leaves N = 4095 and remainder 95.

💡Key takeaway

Counting who you leave out is just as good as counting who you take, and here that single swap turns a difference rule into a size rule: the whole problem becomes "how many subsets of 14 singers have a size that is a multiple of 4?"

Name the two counts
Count the basses you leave out
Merge everything into one pool of 14
List the sizes that survive
Add the four binomial coefficients
Drop the empty group, then divide by 100