AMC10 2019 A

Answer (D): Let $A_n=\dfrac{(n^2-1)!}{(n!)^n}.$ First, note that $A_n$ is an integer when $n=1$. Next, observe that if $n$ is prime, then $A_n$ is not an integer because the numerator has $n-1$ factors of $n$ but the denominator has $n$ such factors. Note also that $A_4$ is not an integer, because the numerator, $15!$, has $7+3+1=11$ factors of $2$, whereas the denominator, $(4!)^4$, has $12$ factors of $2$. Therefore for $n\ge 2$, in order for $A_n$ to be an integer, a necessary condition is that $n$ be composite and greater than $4$. The following argument shows that this condition is also sufficient. First note that $\dfrac{n!}{n^2}=\dfrac{(n-1)!}{n}.$ If $n=ab$, where $a$ and $b$ are distinct positive integers greater than $1$, then $\dfrac{(n-1)!}{n}$ is an integer because both $a$ and $b$ appear as factors in $(n-1)!$. Otherwise $n=p^2$ for some odd prime $p$. In this case $p^2-1\ge 2p$, so $(n-1)!$ has at least two factors of $p$ and again $\dfrac{(n-1)!}{n}$ is an integer. Now the number $\dfrac{(n^2)!}{(n!)^{n+1}}$ is an integer because this expression counts the number of ways to separate $n^2$ objects into $n$ groups of size $n$ without regard to the ordering of the groups (which accounts for the extra factor of $n!$ in the denominator). By combining the previous two paragraphs, it follows that $A_n=\dfrac{(n^2-1)!}{(n!)^n}=\dfrac{(n^2)!}{(n!)^{n+1}}\cdot\dfrac{n!}{n^2}$ is an integer if and only if $n=1$ or $n$ is composite and greater than $4$. Thus the answer is $50$ minus $1$ minus the number of primes less than or equal to $50$, which is $49-15=34$.