2019 AMC 10A Problem 25

Rewrite using $(n^2)! = n^2 \cdot (n^2 - 1)!$:
$$\frac{(n^2-1)!}{(n!)^n} = \frac{(n^2)!}{(n!)^n \cdot n^2}.$$
The number of ways to split $n^2$ labeled objects into $n$ unlabeled groups of $n$ is $\frac{(n^2)!}{(n!)^n \cdot n!}$, an integer $K$. Hence
$$\frac{(n^2-1)!}{(n!)^n} = K \cdot \frac{n!}{n^2} = K \cdot \frac{(n-1)!}{n}.$$
So the expression is certainly an integer whenever $n \mid (n-1)!$.

Composite $n \ge 6$: write $n = ab$ with $1 < a < b < n$, so $a$ and $b$ are distinct factors of $(n-1)!$; if $n = p^2$ with $p \ge 3$, then $p$ and $2p$ both lie below $n$. Either way $n \mid (n-1)!$, and the expression is an integer. Also $n = 1$ gives $\frac{0!}{1} = 1$.

Prime $n = p$: the exponent of $p$ in $(p^2 - 1)!$ is $\lfloor (p^2-1)/p \rfloor = p - 1$, while $(p!)^p$ contains $p^p$. Not an integer.

$n = 4$: the denominator $(4!)^4 = 24^4$ has $2^{12}$, but $15!$ has only $7 + 3 + 1 = 11$ factors of $2$. Not an integer.

Failures: the $15$ primes up to $50$ plus $n = 4$, so $16$ values fail and $50 - 16 = 34$ work.

The answer is $\boxed{\textbf{(D)}\ 34}$.

Two tools cover the problem: a combinatorial interpretation (multinomial and partition counts are integers) proves the "yes" cases in bulk, and Legendre's exponent count $\sum \lfloor m/p^k \rfloor$ settles individual primes. The reduction to $n \mid (n-1)!$ is a classic: it holds for every composite $n$ except $4$, which is exactly the exceptional case here. Check small cases like $n = 4$ by hand whenever a general argument has a boundary condition.

• Counting only the 15 primes as failures (answer 35) and missing that n = 4 also fails, or forgetting that n = 1 works.
• Assuming the sufficient condition $n \mid (n-1)!$ is also necessary without verifying $n = 4$ directly, or counting the primes up to $50$ as $14$ or $16$.