AMC 10 · 2019 · #25

Grade 8 arithmetic

Archetype Small-Domain Constrained Search

factorialprime-numberslegendre-formulacombinatorial-identityprimality-test caseworkcomplementary-countingpattern-recognition ↑ Prerequisites: factorialprime-numberslegendre-formula

📏 Long solution 💡 4 insights

Problem

For how many integers $n$ between $1$ and $50$ , inclusive, is $\frac{(n^2-1)!}{(n!)^n}$ an integer? (Recall that $0! = 1$ .)

$\textbf{(A) } 31 \qquad \textbf{(B) } 32 \qquad \textbf{(C) } 33 \qquad \textbf{(D) } 34 \qquad \textbf{(E) } 35$

Pick an answer.

(A)

(B)

(C)

(D)

(E)

View mode:

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

#9 Solve an Easier Related Problem 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)$.

$$\dfrac{(n^2-1)!}{(n!)^n} = \dfrac{M(n)}{n^2} \;\text{ where } \; M(n) = \dfrac{(n^2)!}{(n!)^n} \in \mathbb{Z}_{>0}$$

💡 The full multinomial is always integral; divisibility by $n^2$ is the only obstruction.

#16 Change Focus / Complement 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$.

$$\text{answer} = 50 - \#\{n : n^2 \nmid M(n)\}$$

💡 Failures may be rare and easy to enumerate — count those instead.

#7 Identify Subproblems 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.

$$v_p(M(p)) = (p+1) - p = 1 < 2$$

💡 Primes $n = p$ lose: numerator gains only one extra factor of $p$ over the denominator, but $n^2 = p^2$ needs two.

#2 Make a Systematic List 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.

$$\#\text{primes in } [1, 50] = 15$$

💡 Primes between $1$ and $50$ are countable by hand.

#5 Look for a Pattern 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.

$$n = 4: \;\; v_2(15!) = 11 < 12 = v_2((4!)^4)$$

💡 Even though $4$ is composite, the multinomial has just barely $11$ factors of $2$ in the numerator vs $12$ in the denominator.

#9 Solve an Easier Related Problem 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.)

$$n = 6: \;\; v_2((6^2-1)!) - v_2((6!)^6) = 32 - 24 = 8 \ge v_2(36) = 2$$

💡 For $n \ne 4$ composite, the numerator $(n^2-1)!$ has so many factors of every prime that divisibility by $n^2$ holds comfortably.

#16 Change Focus / Complement 4.OA.A.3 Step 7

Total failures: $15$ primes $+ 1$ extra ($n = 4$) $= 16$.
Successes: $50 - 16 = 34$.
The answer is (D).

$$50 - 16 = 34$$

💡 Subtract failures from $50$.

[1] #9 6.NS.B.4 Rewrite using the easier problem $M(n) = \dfrac{(n^2)!}{(n!)^n}$ — this is the m

[2] #16 6.NS.B.4 Switch perspective (complement): count $n \in \{1, \ldots, 50\}$ for which $n^2

[3] #7 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] #2 4.OA.B.4 List the primes in $[1, 50]$: $2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 4

[5] #5 8.EE.A.1 Now check small composites for any extra failures. $n = 1$: $\tfrac{0!}{1!^1} =

[6] #9 8.EE.A.1 Verify that every other composite $n$ in $[2, 50]$ works. For composite $n$ (oth

[7] #16 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.3 Solve multi-step word problems using four operations with whole numbers (Final arithmetic $50 - 16 = 34$.)
4.OA.B.4 Find all factor pairs and recognize multiples; determine prime or composite (Listing all primes in $[1, 50]$ and identifying composite candidates.)
6.NS.B.4 Find 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.1 Know 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.

Problem

Toolkit + CCSS Solution

Understand

Plan

Execute — Answer: D

Review

CCSS standards used (min grade 8)

More like this