AMC 10 · 2019 · #25

Grade 8 arithmetic

Archetype Small-Domain Constrained Search └ Sub-archetype Factor / Divisibility Constraint

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

📏 Long solution 💡 4 insights

Problem

For how many integers n from 1 to 50 inclusive is

\frac{(n²-1)!}{(n!)ⁿ}

a whole number?

Pick an answer.

(A)

(B)

(C)

(D)

(E)

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

How to solve

Strategy Solve an Easier Related Problem

Tool #9 (Easier Problem): the related ratio M(n) = $\frac{(n²)!}{(n!)ⁿ}$ is always an integer (it's a multinomial coefficient), and our target equals $\frac{M(n)}{n²}$ . So the question reduces to: for which n does n² divide M(n)? Tool #16 (Complement): instead of counting successes, count failures and subtract from 50. Tool #7 (Subproblems): for any prime p ∣ 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, …) to spot the failure pattern. Tool #2 (Systematic List): list all primes and the special composite n = 4 in [1, 50].

1STEP 1

M(n) = $\frac{(n²)!}{(n!)ⁿ}$ is always a whole number, and the target equals $\frac{M(n)}{n²}$ , so it is an integer exactly when n² ∣ M(n).

\frac{(n²-1)!}{(n!)ⁿ}

\frac{M(n)}{n²}

where M(n) =

\frac{(n²)!}{(n!)ⁿ}

∈ Z_ ＞ 0

2STEP 2

Count by complement: find how many n in 1–50 have n² ∤ M(n) and subtract from 50, using Legendre's formula for prime valuations.

answer = 50 - #{n : n² ∤ M(n)}

3STEP 3

For prime n = p, v_p(M(p)) = (p+1) − p = 1 ＜ 2 = v_p(p²), so p² ∤ M(p): every prime n fails.

v_p(M(p)) = (p+1) - p = 1 ＜ 2

4STEP 4

The primes in 1–50 are 2, 3, 5, …, 47 — there are 15 of them, and each one fails.

#primes in [1, 50] = 15

5STEP 5

Check composites: n = 1 works, but n = 4 fails since v₂(15!) = 11 ＜ 12 = v₂((4!)⁴) — one factor of 2 short.

n = 4: v₂(15!) = 11 ＜ 12 = v₂((4!)⁴)

6STEP 6

Every other composite n works: (n²−1)! carries far more of each prime than (n!)ⁿ·n² needs — e.g. at n = 6 the surplus of 2s is 8 ≥ 2.

n = 6: v₂((6²-1)!) - v₂((6!)⁶) = 32 - 24 = 8 ≥ v₂(36) = 2

7STEP 7

Failures total 15 primes + 1 (n = 4) = 16, so successes are 50 − 16 = 34 — answer (D).

50 - 16 = 34

Answer

Spot checks. n = 1:

\frac{0!}{1!¹}

= 1 ✓ (composite/unit treated as success per the count). n = 2 (prime):

\frac{3!}{2!²}

\frac{6}{4}

= 1.5, fail ✓. n = 3 (prime):

\frac{8!}{6³}

\frac{40320}{216}

= 186.6, fail ✓. n = 4:

\frac{15!}{24⁴}

\frac{1307674368000}{331776}

≈ 3.94 · 10⁶ — check v₂: numerator 11 vs denominator 12, ratio has v₂ = -1, so not integer ✓. n = 6 (composite): v₂ comfortably positive as shown. n = 9 = 3²: v₃(80!) = 26 + 8 + 2 = 36 and v₃((9!)⁹) = 9 · 4 = 36, so v₃(ratio) = 36 - 36 = 0 ≥ v₃(81) = 4? Wait — we need ≥ v₃(81) = 4, and 0 ＜ 4. Recompute: we need v₃(M(9)) ≥ v₃(81) = 4 where M(9) =

\frac{(81)!}{(9!)⁹}

. v₃(81!) = 27 + 9 + 3 + 1 = 40, v₃((9!)⁹) = 9 · v₃(9!) = 9 · 4 = 36. v₃(M(9)) = 40 - 36 = 4 ≥ 4 ✓. So n = 9 works. The argument fits: every composite n ≠ 4 succeeds.

💡Key takeaway

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