AMC 10 · 2024 · #22

Grade 8 counting

Archetype Arithmetic Expression Decomposition

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

📏 Long solution 💡 3 insights

Problem

A group of $16$ people will be partitioned into $4$ indistinguishable $4$ -person committees. Each committee will have one chairperson and one secretary. The number of different ways to make these assignments can be written as $3^{r}M$ , where $r$ and $M$ are positive integers and $M$ is not divisible by $3$ . What is $r$ ?

$\textbf{(A) }5 \qquad \textbf{(B) }6 \qquad \textbf{(C) }7 \qquad \textbf{(D) }8 \qquad \textbf{(E) }9 \qquad$

Pick an answer.

(A)

(B)

(C)

(D)

(E)

View mode:

Toolkit + CCSS Solution

Understand

Restated: $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$.

Givens: $16$ people, $4$ committees, each of size $4$; Committees are indistinguishable (unordered groups); Each committee picks $1$ chair and $1$ secretary from its $4$ members; $N = 3^{r} M$, $r, M$ positive integers, $3 \nmid M$; Answer choices: (A) $5$, (B) $6$, (C) $7$, (D) $8$, (E) $9$

Unknowns: The exponent $r$ — the largest power of $3$ dividing $N$

Understand

Plan

Primary tool: #7 Identify Subproblems

Secondary: #13 Convert to Algebra, #5 Look for a Pattern, #8 Analyze the Units

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!)^5$, (ii) the role count $12^4$ per committee. Tool #13 (Convert to Algebra) gives the formula $N = 16! \cdot 12^4 / (4!)^5$. 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, \dots$ plus extras from $p^2, 2p^2, \dots$ (Legendre). Tool #8 (Analyze the Units) finally treats the prime $3$ as the "unit" we are counting and tracks $v_3$ through the product, turning a hard combinatorics problem into one $v_3$ accounting sheet.

Execute — Answer: A

#7 Identify Subproblems 7.SP.C.8 Step 1

Split $N$ into clean subproblems.
Step (a) partition $16$ people into $4$ ordered groups of $4$: this is $\binom{16}{4}\binom{12}{4}\binom{8}{4}\binom{4}{4} = \dfrac{16!}{(4!)^4}$.
Step (b) the committees are indistinguishable, so divide by $4!$ to undo the ordering: $\dfrac{16!}{(4!)^5}$.
Step (c) each committee picks $1$ chair and $1$ secretary — $4 \times 3 = 12$ ways per committee, $12^4$ across all four.
Multiply.

$$N = \dfrac{16!}{(4!)^5} \cdot 12^4 = \dfrac{16! \cdot 12^4}{(4!)^5}$$

💡 Grade 7 organized counting principle: each independent stage contributes a factor, and the indistinguishable committees cost one $4!$ in the denominator.

#13 Convert to Algebra 8.EE.A.1 Step 2

We need only the power of $3$ in $N$.
Let $v_3(x)$ denote the exponent of $3$ in $x$'s prime factorization.
Then $v_3(N) = v_3(16!) + v_3(12^4) - v_3((4!)^5)$ because $v_3$ adds across products and subtracts across quotients.

$$r = v_3(N) = v_3(16!) + v_3(12^4) - v_3((4!)^5)$$

💡 Grade 8 integer-exponent rules: $v_3$ is just a counter, and exponent rules turn multiplication into addition, division into subtraction.

#5 Look for a Pattern 6.NS.B.4 Step 3

Compute $v_3(16!)$ by Legendre's pattern.
The multiples of $3$ in $\{1, 2, \dots, 16\}$ are $3, 6, 9, 12, 15$ — five of them, each contributing one factor of $3$.
The multiples of $9$ are $9$ alone — one extra factor of $3$.
No multiples of $27$ inside $16$.
Add: $5 + 1 = 6$.

$$v_3(16!) = \lfloor 16/3 \rfloor + \lfloor 16/9 \rfloor + \lfloor 16/27 \rfloor + \dots = 5 + 1 + 0 = 6$$

💡 Grade 6 multiples-and-factors: walk up by multiples of $3$, then multiples of $9$, etc., each tier adds one more $3$ to the running count.

#13 Convert to Algebra 8.EE.A.1 Step 4

Compute $v_3(12^4)$.
Since $12 = 4 \cdot 3 = 2^2 \cdot 3$, we have $v_3(12) = 1$.
Raising to the $4$th power multiplies the exponent: $v_3(12^4) = 4 \cdot 1 = 4$.

$$12 = 2^2 \cdot 3 \;\Rightarrow\; v_3(12^4) = 4 \cdot v_3(12) = 4$$

💡 Grade 8 exponent rule $(a \cdot b)^n = a^n b^n$: a single factor of $3$ in the base becomes $4$ factors when raised to the $4$th.

#13 Convert to Algebra 8.EE.A.1 Step 5

Compute $v_3((4!)^5)$.
Since $4! = 24 = 2^3 \cdot 3$, we have $v_3(4!) = 1$.
Raising to the $5$th power: $v_3((4!)^5) = 5 \cdot 1 = 5$.

$$4! = 24 = 2^3 \cdot 3 \;\Rightarrow\; v_3((4!)^5) = 5 \cdot v_3(4!) = 5$$

💡 Grade 8 same exponent rule applied to the denominator.

#8 Analyze the Units 8.EE.A.1 Step 6

Combine the three pieces.

$$r = v_3(N) = 6 + 4 - 5 = 5 \;\Rightarrow\; \textbf{(A)}$$

💡 Grade 8 integer-exponent accounting closes the problem — same idea as tracking units, just for the prime $3$.

[1] #7 7.SP.C.8 Split $N$ into clean subproblems. Step (a) partition $16$ people into $4$ ordere

[2] #13 8.EE.A.1 We need only the power of $3$ in $N$. Let $v_3(x)$ denote the exponent of $3$ in

[3] #5 6.NS.B.4 Compute $v_3(16!)$ by Legendre's pattern. The multiples of $3$ in ${1, 2, \dots

[4] #13 8.EE.A.1 Compute $v_3(12^4)$. Since $12 = 4 \cdot 3 = 2^2 \cdot 3$, we have $v_3(12) = 1$

[5] #13 8.EE.A.1 Compute $v_3((4!)^5)$. Since $4! = 24 = 2^3 \cdot 3$, we have $v_3(4!) = 1$. Rai

[6] #8 8.EE.A.1 Combine the three pieces.

Review

Reasonableness: Sanity check the magnitudes. The numerator $16!$ alone donates six $3$s (five from $3, 6, 9, 12, 15$ plus one extra from $9 = 3^2$); the role factor $12^4$ adds four more for a total of ten in the numerator; the denominator $(4!)^5$ siphons five back, leaving $10 - 5 = 5$. Every count in the breakdown is a small whole number ($\le 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_3(4!) = 1$, pushing $r$ from $5$ to $6$, exactly the off-by-one trap (B).

Alternative: Tool #15 (Reorganize Information): rewrite $N = \dfrac{16!}{(4!)^5} \cdot 12^4 = \dfrac{16! \cdot (2^2 \cdot 3)^4}{(2^3 \cdot 3)^5} = \dfrac{16! \cdot 2^8 \cdot 3^4}{2^{15} \cdot 3^5} = \dfrac{16!}{2^7 \cdot 3}$. Now $r = v_3(N) = v_3(16!) - 1 = 6 - 1 = 5$. The reorganization makes the $3$-count almost obvious in a single line.

CCSS standards used (min grade 8)

7.SP.C.8 Find probabilities of compound events using organized lists, tables, tree diagrams, and simulation — including counting by the fundamental counting principle (Counting $N$ as a product of independent stages: partition into ordered groups, divide by $4!$ for indistinguishable committees, multiply by $12$ role-assignment choices per committee.)
6.NS.B.4 Find the greatest common factor of two whole numbers less than or equal to 100 and the least common multiple of two whole numbers less than or equal to 12 — extending to counting prime factors (Walking up through the multiples of $3$ and $9$ in $\{1, \dots, 16\}$ to add up $v_3(16!) = 5 + 1 = 6$ (Legendre's pattern).)
8.EE.A.1 Know and apply the properties of integer exponents to generate equivalent numerical expressions (Using $v_3(a \cdot b) = v_3(a) + v_3(b)$ and $v_3(a^n) = n \cdot v_3(a)$ to combine $v_3(16!) + v_3(12^4) - v_3((4!)^5) = 6 + 4 - 5 = 5$.)

⭐ 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^4$, but five get cancelled by $(4!)^5$, leaving exactly $r = 5$.

Problem

Toolkit + CCSS Solution

Understand

Plan

Execute — Answer: A

Review

CCSS standards used (min grade 8)

More like this