# Difference between revisions of "2019 AMC 10A Problems/Problem 25"

The following problem is from both the 2019 AMC 10A #25 and 2019 AMC 12A #24, so both problems redirect to this page.

## Problem

For how many integers $n$ between $1$ and $50$, inclusive, is $$\frac{(n^2-1)!}{(n!)^n}$$ an integer? (Recall that $0! = 1$.) $\textbf{(A) } 31 \qquad \textbf{(B) } 32 \qquad \textbf{(C) } 33 \qquad \textbf{(D) } 34 \qquad \textbf{(E) } 35$

## Solution

### Solution 1

The main insight is that $$\frac{(n^2)!}{(n!)^{n+1}}$$

is always an integer. This is true because it is precisely the number of ways to split up $n^2$ objects into $n$ unordered groups of size $n$. Thus, $$\frac{(n^2-1)!}{(n!)^n}=\frac{(n^2)!}{(n!)^{n+1}}\cdot\frac{n!}{n^2}$$

is an integer if $n^2 \mid n!$, or in other words, if $n \mid (n-1)!$. This condition is false precisely when $n=4$ or $n$ is prime, by Wilson's Theorem. There are $15$ primes between $1$ and $50$, inclusive, so there are $15 + 1 = 16$ terms for which $$\frac{(n^2-1)!}{(n!)^{n}}$$

is potentially not an integer. It can be easily verified that the above expression is not an integer for $n=4$ as there are more factors of $2$ in the denominator than the numerator. Similarly, it can be verified that the above expression is not an integer for any prime $n=p$, as there are more factors of p in the denominator than the numerator. Thus all $16$ values of n make the expression not an integer and the answer is $50-16=\boxed{\textbf{(D)}\ 34}$.

### Solution 2

We can use the P-Adic Valuation (more info could be found here: Mathematicial notation) of n to solve this problem (recall the P-Adic Valuation of 'n' is denoted by $v_p (n)$ and is defined as the greatest power of some prime 'p' that divides n. For example, $v_2 (6)=1$ or $v_7 (245)=2$ .) Using Legendre's formula, we know that : $$v_p (n!)= \sum_{i=1}^\infty \lfloor \frac {n}{p^i} \rfloor$$

Seeing factorials involved in the problem, this prompts us to use Legendre's formula where n is a power of a prime.

We also know that , $v_p (m^n) = n \cdot v_p (m)$ . Knowing that $a\mid b$ if $v_p (a) \le v_p (b)$ , we have that : $$n \cdot v_p (n!) \le v_p ((n^2 -1 )!)$$ and we must find all n for which this is true.

If we plug in $n=p$, by Legendre's we get two equations: $$v_p ((n^2 -1)!) = \sum_{i=1}^\infty \lfloor \frac {n^2 -1}{p^i} \rfloor = (p-1)+0+...+0 = p-1$$

And we also get : $$v_p ((n!)^n) = n \cdot v_p (n!)= n \cdot \sum_{i=1}^\infty \lfloor \frac {n}{p^i} \rfloor = p \cdot ( 1+0+...0) = p$$

But we are asked to prove that $n \cdot v_p (n!) \le v_p ((n^2 -1 )!) \Longrightarrow p \le p-1$ which is false for all 'n' where n is prime.

Now we try the same for $n=p^2$ , where p is a prime. By Legendre we arrive at: $$v_p ((p^4 -1)!) = p^3 + p^2 + p -3$$ and $$p^2 \cdot v_p (p^2 !) = p^3 + p^2$$

Then we get: $$p^2 \cdot v_p (p!) \le v_p ((n^4 -1)!) \Longrightarrow p^3 + p^2 \le p^3 + p^2 + p -3$$ Which is true for all primes except for 2, so $2^2 = 4$ doesn't work. It can easily be verified that for all $n=p^i$ where $i$ is an integer greater than 2, satisfies the inequality : $$n \cdot v_p (n!) \le v_p ((n^2 -1 )!).$$

Therefore, there are 16 values that don't work and $50-16 = \boxed{\mathbf{(D)}\ 34}$ values that work.

~qwertysri987

## Solution 3 (Guessing)

First, we see that $n=1, 6, 8, 9, 10, 12, 14$ work. This leads us to the conclusion of $50-16 = \boxed{\textbf{(D)}\ 34}$

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. 