AMC 10 · 2019 · #25
Grade 8 arithmeticProblem
For how many integers n between 1 and 50, inclusive, is (n!)n(n2−1)! an integer? (Recall that 0!=1.)
Pick an answer.
AMC 10 2019 problem © Mathematical Association of America (MAA AMC). Reproduced for educational use.
Try it yourself first — the explanation is most useful after you’ve attempted it.
Toolkit + CCSS Solution
Understand
Restated: For how many integers $n$ from $1$ to $50$ inclusive is $\dfrac{(n^2-1)!}{(n!)^n}$ a whole number?
Givens: $n$ ranges over $\{1, 2, 3, \ldots, 50\}$; Numerator: $(n^2 - 1)!$; Denominator: $(n!)^n$; $0! = 1$; Answer choices: (A) $31$, (B) $32$, (C) $33$, (D) $34$, (E) $35$
Unknowns: The count of $n$ for which $\dfrac{(n^2-1)!}{(n!)^n}$ is an integer
Understand
Restated: For how many integers $n$ from $1$ to $50$ inclusive is $\dfrac{(n^2-1)!}{(n!)^n}$ a whole number?
Givens: $n$ ranges over $\{1, 2, 3, \ldots, 50\}$; Numerator: $(n^2 - 1)!$; Denominator: $(n!)^n$; $0! = 1$; Answer choices: (A) $31$, (B) $32$, (C) $33$, (D) $34$, (E) $35$
Plan
Primary tool: #9 Solve an Easier Related Problem
Secondary: #7 Identify Subproblems, #5 Look for a Pattern, #16 Change Focus / Complement, #2 Make a Systematic List
Tool #9 (Easier Problem): the related ratio $M(n) = \tfrac{(n^2)!}{(n!)^n}$ is always an integer (it's a multinomial coefficient), and our target equals $M(n)/n^2$. So the question reduces to: for which $n$ does $n^2$ divide $M(n)$? Tool #16 (Complement): instead of counting successes, count failures and subtract from $50$. Tool #7 (Subproblems): for any prime $p \mid n$, check the $p$-adic valuation $v_p$ of numerator and denominator using Legendre. Tool #5 (Pattern): test small $n$ ($n=1, 2, 3, 4, 5, 6, \ldots$) to spot the failure pattern. Tool #2 (Systematic List): list all primes and the special composite $n = 4$ in $[1, 50]$.
Execute — Answer: D
6.NS.B.4 Step 1 - Rewrite using the easier problem $M(n) = \dfrac{(n^2)!}{(n!)^n}$ — this is the multinomial $\binom{n^2}{n, n, \ldots, n}$ (number of ordered partitions of $n^2$ distinct objects into $n$ blocks of size $n$), always a positive integer.
- Then $\dfrac{(n^2-1)!}{(n!)^n} = \dfrac{(n^2)!}{(n!)^n \cdot n^2} = \dfrac{M(n)}{n^2}$.
- So the ratio is an integer iff $n^2 \mid M(n)$.
💡 The full multinomial is always integral; divisibility by $n^2$ is the only obstruction.
6.NS.B.4 Step 2 - Switch perspective (complement): count $n \in \{1, \ldots, 50\}$ for which $n^2 \nmid M(n)$, then subtract from $50$.
- Use Legendre's formula for the $p$-adic valuation: $v_p(k!) = \sum_{i \ge 1} \lfloor k/p^i \rfloor$.
💡 Failures may be rare and easy to enumerate — count those instead.
6.NS.B.4 Step 3 - Case: $n$ is prime, say $n = p$.
- We need $v_p(M(p)) \ge v_p(p^2) = 2$.
- Compute $v_p((p^2)!) = \lfloor p^2/p \rfloor + \lfloor p^2/p^2 \rfloor = p + 1$ and $v_p((p!)^p) = p \cdot v_p(p!) = p \cdot 1 = p$.
- So $v_p(M(p)) = (p + 1) - p = 1 < 2$.
- Hence $p^2 \nmid M(p)$ — every prime $n$ fails.
💡 Primes $n = p$ lose: numerator gains only one extra factor of $p$ over the denominator, but $n^2 = p^2$ needs two.
4.OA.B.4 Step 4 - List the primes in $[1, 50]$: $2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47$ — that's $15$ primes.
- Each fails.
💡 Primes between $1$ and $50$ are countable by hand.
8.EE.A.1 Step 5 - Now check small composites for any extra failures.
- $n = 1$: $\tfrac{0!}{1!^1} = 1$.
- ✓ integer.
- $n = 4$: numerator $15!$, denominator $(4!)^4 = 24^4$.
- Use Legendre at $p = 2$: $v_2(15!) = 7 + 3 + 1 = 11$ and $v_2(24^4) = 4 \cdot v_2(24) = 4 \cdot 3 = 12$.
- So $v_2(\text{ratio}) = 11 - 12 = -1 < 0$ — not an integer!
- So $n = 4$ fails too.
💡 Even though $4$ is composite, the multinomial has just barely $11$ factors of $2$ in the numerator vs $12$ in the denominator.
8.EE.A.1 Step 6 - Verify that every other composite $n$ in $[2, 50]$ works.
- For composite $n$ (other than $4$), $n$ has a prime factor $p$ with $p^k \| n$ for $k \ge 1$, and the standard estimate from Legendre gives $v_p((n^2-1)!) \ge v_p((n!)^n) + v_p(n^2)$ — concretely, the count of multiples of $p$ in $\{1, \ldots, n^2 - 1\}$ comfortably exceeds $n$ copies of $v_p(n!)$ plus $v_p(n^2)$ whenever $n$ is composite and $n \ne 4$.
- (Sample check at $n = 6$: $v_2(35!) = 17 + 8 + 4 + 2 + 1 = 32$ and $v_2((6!)^6) = 6 \cdot v_2(720) = 6 \cdot 4 = 24$; need $\ge v_2(36) = 2$ extra, and $32 - 24 = 8 \ge 2$.
- Same kind of check at $p = 3$ and other primes goes through.)
💡 For $n \ne 4$ composite, the numerator $(n^2-1)!$ has so many factors of every prime that divisibility by $n^2$ holds comfortably.
4.OA.A.3 Step 7 - Total failures: $15$ primes $+ 1$ extra ($n = 4$) $= 16$.
- Successes: $50 - 16 = 34$.
- The answer is (D).
💡 Subtract failures from $50$.
6.NS.B.4 Rewrite using the easier problem $M(n) = \dfrac{(n^2)!}{(n!)^n}$ — this is the m 6.NS.B.4 Switch perspective (complement): count $n \in \{1, \ldots, 50\}$ for which $n^2 6.NS.B.4 Case: $n$ is prime, say $n = p$. We need $v_p(M(p)) \ge v_p(p^2) = 2$. Compute $ 4.OA.B.4 List the primes in $[1, 50]$: $2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 4 8.EE.A.1 Now check small composites for any extra failures. $n = 1$: $\tfrac{0!}{1!^1} = 8.EE.A.1 Verify that every other composite $n$ in $[2, 50]$ works. For composite $n$ (oth 4.OA.A.3 Total failures: $15$ primes $+ 1$ extra ($n = 4$) $= 16$. Successes: $50 - 16 = Review
Reasonableness: Spot checks. $n = 1$: $\tfrac{0!}{1!^1} = 1$ ✓ (composite/unit treated as success per the count). $n = 2$ (prime): $\tfrac{3!}{2!^2} = \tfrac{6}{4} = 1.5$, fail ✓. $n = 3$ (prime): $\tfrac{8!}{6^3} = \tfrac{40320}{216} = 186.\overline{6}$, fail ✓. $n = 4$: $\tfrac{15!}{24^4} = \tfrac{1307674368000}{331776} \approx 3.94 \cdot 10^6$ — check $v_2$: numerator $11$ vs denominator $12$, ratio has $v_2 = -1$, so not integer ✓. $n = 6$ (composite): $v_2$ comfortably positive as shown. $n = 9 = 3^2$: $v_3(80!) = 26 + 8 + 2 = 36$ and $v_3((9!)^9) = 9 \cdot 4 = 36$, so $v_3(\text{ratio}) = 36 - 36 = 0 \ge v_3(81) = 4$? Wait — we need $\ge v_3(81) = 4$, and $0 < 4$. Recompute: we need $v_3(M(9)) \ge v_3(81) = 4$ where $M(9) = (81)!/(9!)^9$. $v_3(81!) = 27 + 9 + 3 + 1 = 40$, $v_3((9!)^9) = 9 \cdot v_3(9!) = 9 \cdot 4 = 36$. $v_3(M(9)) = 40 - 36 = 4 \ge 4$ ✓. So $n = 9$ works. The argument fits: every composite $n \ne 4$ succeeds.
Alternative: Tool #6 (Guess and Check) by brute computation in a small spreadsheet: for $n = 1, 2, \ldots, 50$ compute the $p$-adic valuations of $(n^2 - 1)!$ vs $(n!)^n$ for each prime $p$ dividing $n$. Verify the ratio is non-negative iff $n \in \{1\} \cup \{\text{composites} \setminus \{4\}\}$. Counting: $50$ total $- 15$ primes $- 1$ ($n = 4$) $= 34$. Same answer; the analytic route is faster but the spreadsheet confirms the lone composite failure at $n = 4$.
CCSS standards used (min grade 8)
4.OA.A.3Solve multi-step word problems using four operations with whole numbers (Final arithmetic $50 - 16 = 34$.)4.OA.B.4Find all factor pairs and recognize multiples; determine prime or composite (Listing all primes in $[1, 50]$ and identifying composite candidates.)6.NS.B.4Find greatest common factor and least common multiple of two numbers (Reducing the divisibility question to whether $n^2$ divides the multinomial $M(n) = (n^2)!/(n!)^n$.)8.EE.A.1Know and apply the properties of integer exponents (Tracking the highest power of each prime via Legendre's formula $v_p(k!) = \sum_i \lfloor k/p^i \rfloor$ and comparing exponents in numerator vs denominator.)
⭐ This AMC 10 problem only needs Grade 8 exponent tracking (Legendre's formula for prime powers in factorials) plus primality you already know — every prime $n$ in $[1, 50]$ fails ($15$ of them) and $n = 4$ also fails (numerator short one factor of $2$), so $50 - 16 = 34$ values work.
⭐ This AMC 10 problem only needs Grade 8 exponent tracking (Legendre's formula for prime powers in factorials) plus primality you already know — every prime $n$ in $[1, 50]$ fails ($15$ of them) and $n = 4$ also fails (numerator short one factor of $2$), so $50 - 16 = 34$ values work.
More like this
Same archetype — closest grade level first.
