AMC 10 · 2024 · #22

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)

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

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 $\frac{16!}{(4!)⁵}$ , (ii) the role count 12⁴ per committee. Tool #13 (Convert to Algebra) gives the formula N = 16! · $\frac{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

Split N into three factors: group partition, one 4! for indistinguishable committees, 12 role-picks each — so N = 16! · $\frac{12⁴}{(4!)⁵}$ .

N =

\frac{16!}{(4!)⁵}

· 12⁴ =

\frac{16! · 12⁴}{(4!)⁵}

2STEP 2

Only the power of 3 matters. Writing v₃ for the exponent of 3, products add and quotients subtract: v₃(N) = v₃(16!) + v₃(12⁴) - v₃((4!)⁵).

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

3STEP 3

Count 3s in 16! by tiers: multiples of 3 (3,6,9,12,15) give five, the multiple of 9 gives one more, none for 27 — so v₃(16!) = 6.

v₃(16!) = ⌊

\frac{16}{3}

⌋ + ⌊

\frac{16}{9}

⌋ + ⌊

\frac{16}{27}

⌋ + … = 5 + 1 + 0 = 6

4STEP 4

Since 12 = 2² · 3, v₃(12) = 1; the 4th power multiplies it, so v₃(12⁴) = 4.

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

5STEP 5

Since 4! = 24 = 2³ · 3, v₃(4!) = 1; raising to the 5th power gives v₃((4!)⁵) = 5.

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

6STEP 6

Add the three counts — 6 + 4 - 5 = 5 — so r = 5, choice (A).

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.

More like this