AMC 10 · 2019 · #24
Grade 8 number-theoryPick an answer.
Tool #9 (Easier Problem): the related ratio M(n) = (n²)!/(n!)ⁿ is always an integer (it's a multinomial coefficient), and our target equals 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].
Rewrite with a familiar quantity
It is a multinomial coefficient over n squared.
The full multinomial is always integral; divisibility by n² is the only obstruction.
6.NS.B.4Solve An Easier Related ProblemCount the complement
It is faster to subtract the failures.
Failures may be rare and easy to enumerate — count those instead.
6.NS.B.4Change Focus Count The ComplementPrimes always fail
For a prime the exponent falls one short.
Primes n = p lose: numerator gains only one extra factor of p over the denominator, but n² = p² needs two.
A prime fails because the numerator gains only one extra copy of it while the square demands two.
▸ Why?
Every number has one prime recipe, so the count of each prime can be tallied exactly.
▸ Why?
Divisibility asks only whether enough copies are present, and one short is enough to fail.
Count the primes
There are fifteen primes in range.
Primes between 1 and 50 are countable by hand.
4.OA.B.4Make A Systematic ListFind the composite exception
At four the exponent also falls short.
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.1Look For A PatternCheck the other composites
Other composites have room to spare.
For n ≠ 4 composite, the numerator (n²-1)! has so many factors of every prime that divisibility by n² holds comfortably.
8.EE.A.1Solve An Easier Related ProblemSubtract to finish
Subtracting gives 34.
Subtract failures from 50.
4.OA.A.3Change Focus Count The ComplementThis AMC 12 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.