AMC 10 · 2024 · #16

Grade 8 counting

Archetype Arithmetic Expression Decomposition └ Sub-archetype Successive Multiplicative Steps

combinations-basicfactorialprime-factorizationlegendre-formula identify-subproblemsconvert-to-algebrapattern-recognition ↑ Prerequisites: combinations-basicfactorialprime-factorization

📏 Long solution 💡 3 insights

Problem

16 people are split into 4 indistinguishable committees of 4, and inside each committee one chair and one secretary are chosen. Let N be the total number of such labeled arrangements. Write N = 3^r M with M not divisible by 3. Find r.

Pick an answer.

(A)

(B)

(C)

(D)

(E)

How to solve

Strategy Identify Subproblems

We do not need the value of N — only the power of 3 inside it. Tool #7 (Identify Subproblems) splits N into a clean product: (i) the partition count 16!/(4!)⁵, (ii) the role count 12⁴ per committee. Tool #13 (Convert to Algebra) gives the formula N = 16! · 12⁴ / (4!)⁵. Tool #5 (Look for a Pattern) replaces the impossible-to-compute number with a place-value style pattern — for any prime p, the exponent of p in n! is the count of p's contributed by p, 2p, 3p, … plus extras from p², 2p², … (Legendre). Tool #8 (Analyze the Units) finally treats the prime 3 as the "unit" we are counting and tracks v₃ through the product, turning a hard combinatorics problem into one v₃ accounting sheet.

1STEP 1

Write the count as a formula

Splitting times choosing gives a factorial formula.

N = 16!/(4!)⁵ · 12⁴ = (16! · 12⁴)/(4!)⁵

2STEP 2

Track only the exponent of 3

Exponents just add and subtract.

r = v₃(N) = v₃(16!) + v₃(12⁴) - v₃((4!)⁵)

3STEP 3

The exponent inside 16 factorial

Legendre gives 6.

v₃(16!) = ⌊ 16/3 ⌋ + ⌊ 16/9 ⌋ + ⌊ 16/27 ⌋ + … = 5 + 1 + 0 = 6

4STEP 4

The exponent inside twelve to the fourth

One three per twelve gives 4.

12 = 2² · 3 → v₃(12⁴) = 4 · v₃(12) = 4

5STEP 5

The exponent in the denominator

Five copies of four factorial give 5.

4! = 24 = 2³ · 3 → v₃((4!)⁵) = 5 · v₃(4!) = 5

6STEP 6

Add and subtract

Six plus four minus five is 5.

r = v₃(N) = 6 + 4 - 5 = 5 → (A)

Answer

Sanity check the magnitudes. The numerator 16! alone donates six 3s (five from 3, 6, 9, 12, 15 plus one extra from 9 = 3²); the role factor 12⁴ adds four more for a total of ten in the numerator; the denominator (4!)⁵ siphons five back, leaving 10 - 5 = 5. Every count in the breakdown is a small whole number ( ≤ 6), so a five-power answer is reasonable, and choices 5, 6, 7, 8, 9 are tightly clustered around it. A common error would be forgetting to divide by 4! for indistinguishable committees — that mistake costs v₃(4!) = 1, pushing r from 5 to 6, exactly the off-by-one trap (B).

💡Key takeaway

When a huge counting answer asks "how many threes hide inside?", do not compute the answer — just count threes piece by piece. Five threes come from 16!, four more from 12⁴, but five get cancelled by (4!)⁵, leaving exactly r = 5.