2019 AMC 10A Problem 25

Step 1: try small cases.

• $n = 1$: $\frac{0!}{1!} = 1$. Whole number.
• $n = 2$: $\frac{3!}{(2!)^2} = \frac{6}{4}$. Not whole.
• $n = 3$: $\frac{8!}{(3!)^3} = \frac{40320}{216} = 186.67\ldots$. Not whole.
• $n = 4$: $\frac{15!}{(4!)^4}$. We will see below that this is not whole.

So some values fail. We need a way to sort all $50$.

Step 2: a counting fact. Split $n^2$ people into $n$ teams of $n$ people each, where the teams have no names (only who is with whom matters). The number of ways is
$$K = \frac{(n^2)!}{(n!)^n \cdot n!}.$$
(Line everyone up in $(n^2)!$ ways and cut into blocks of $n$; each team's order inside does not matter, divide by $n!$ for each of the $n$ teams; the order of the teams does not matter, divide by another $n!$.) Since $K$ counts something, it is a whole number.

Step 3: rewrite the fraction using $K$. Since $(n^2)! = n^2 \cdot (n^2 - 1)!$,
$$\frac{(n^2-1)!}{(n!)^n} = \frac{(n^2)!}{(n!)^n \cdot n^2} = K \cdot \frac{n!}{n^2} = K \cdot \frac{(n-1)!}{n}.$$
So the fraction is surely a whole number whenever $n$ divides $(n-1)! = 1 \cdot 2 \cdots (n-1)$.

Step 4: $n$ not prime and at least 6 always works.

• If $n = a \cdot b$ with $a$ and $b$ different and both smaller than $n$ (like $12 = 3 \cdot 4$), then both $a$ and $b$ appear in $1 \cdot 2 \cdots (n-1)$, so $n$ divides it.
• If $n$ is a prime $p$ squared with $p$ at least $3$, like $9 = 3 \cdot 3$ or $25 = 5 \cdot 5$, then $p$ and $2p$ both appear below $n$ (for $9$: $3$ and $6$), giving at least two factors of $p$.

Step 5: primes always fail. Take $n = p$ prime. The bottom $(p!)^p$ has $p$ factors of $p$ (one from each $p!$). The top $(p^2 - 1)!$ gets a factor of $p$ only from the multiples $p, 2p, \ldots, (p-1)p$, which is just $p - 1$ factors. There are more $p$'s on the bottom than on the top, so it is not whole.

Step 6: $n = 4$ fails. The bottom $(4!)^4 = 24^4$ has $3 \cdot 4 = 12$ factors of $2$. In the top, $15!$: the even numbers up to $15$ give $7$ factors of $2$, the multiples of $4$ give $3$ more, and $8$ gives $1$ more, for $11$ in all. $11 < 12$, so it is not whole.

Step 7: count. The primes up to $50$ are $2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47$: fifteen of them. Adding $n = 4$ gives $16$ failures. Every other $n$ (including $1$) works, so the count is $50 - 16 = 34$.

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

A fraction that counts something must be a whole number, which is a quick way to prove many cases at once. For the cases that fail, count how many times a prime appears on top and on bottom. The leftover question "does $n$ divide $(n-1)!$?" has a well-known answer: yes for every non-prime $n$ except $4$, which is exactly the surprise value here.

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}$.