AMC 10 · 2003 · #20

Grade 11 counting
Archetype Casework by Position / Vertex Type └ Sub-archetype Count of Type
combinations-basicfundamental-counting-principlecombinatorial-identity caseworkidentify-subproblems ↑ Prerequisites: combinations-basic
📏 Long solution 💡 3 insights
Problem
Build a 15-letter string out of five A's, five B's, and five C's. Split the string into three blocks of five. The first block may contain no A, the second block no B, the third block no C. Count how many such strings exist, and match the count to one of the five given expressions.

Pick an answer.

(A)
$\sum_{k=0}^{5}\binom{5}{k}^{3}$
(B)
$3^{5}\cdot 2^{5}$
(C)
$2^{15}$
(D)
$\frac{15!}{(5!)^{3}}$
(E)
$3^{15}$
How to solve
Strategy Introduce a Variable

Each restriction is a ban, so first flip it into what is allowed (Tool #16): every block draws from only two letters. That makes each block a simple choose-the-positions job. The whole problem then hinges on one number — how many B's sit in block 1 — so name it k (Tool #4) and chase the consequences. Every other block count is forced by the requirement that each letter is used exactly five times overall, which turns the counting into three independent subproblems (Tool #7) whose answers multiply. Different values of k give different strings, so the six values k=0,1,…,5 can be listed and added (Tool #2). The final numeric comparison against the other four expressions (Tool #3) is a check on the derived formula, not the reason for it.

1STEP 1

Turn each ban into a two-letter menu

Each ban leaves a two-letter menu, so every block is built from just two letters.

block 1 ∈ {B,C}, block 2 ∈ {C,A}, block 3 ∈ {A,B}
2STEP 2

One number controls the whole string

Naming one count k forces every other count, and the totals check out.

block 1: k B, (5-k) C; block 2: (5-k) A, k C; block 3: k A, (5-k) B
3STEP 3

Count the arrangements for a fixed k

Each block is then a choice of positions, so a fixed k contributes C(5,k) cubed.

C(5, k)·C(5, k)·C(5, k)=C(5, k)³
4STEP 4

Add the six cases

The six values of k never overlap, so the total is their sum.

total=Σ_k=0⁵C(5, k)³
5STEP 5

Confirm against the other expressions

Evaluating gives 2252, matching none of the others, so the answer is the sum of cubes, choice (A).

Σ_k=0⁵C(5, k)³=2(1+125+1000)=2252
Answer
Σ_k=0⁵C(5, k)³
Shrink the problem and count by hand. With one letter of each kind and blocks of size 1, the rule says position 1 is not A, position 2 is not B, position 3 is not C — that is exactly a derangement of A, B, C, and there are 2 of them (BCA and CAB). The formula gives Σ_k=0¹C(1, k)³=1+1=2, a match. With two of each letter and blocks of size 2, direct counting gives 10 and the formula gives C(2, 0)³+C(2, 1)³+C(2, 2)³=1+8+1=10, another match. Two endpoints also behave: k=0 forces block 1 to be all C, block 2 all A, block 3 all B, exactly one string, and C(5, 0)³=1; the same at k=5. Finally 2252 sits comfortably below the unrestricted total 756756, as a restricted count must.
💡Key takeaway

When every block is missing a different letter, one count controls all the others, so pick that count, multiply the three block choices, and add over its possible values.

  • Turn each ban into a two-letter menu
  • One number controls the whole string
  • Count the arrangements for a fixed k
  • Add the six cases
  • Confirm against the other expressions

More like this

Same archetype — closest grade level first.