I'm going over some AMC problem. It's 2019 AMC 10A #25. I was going over some solutions and I got stuck in one part.
They say:$\frac{(n^2)!}{(n!)^{n+1}}\cdot\frac{n!}{n^2}$ is an integer, if $\frac{n!}{n^2}$ is an integer, since $\frac{(n^2)!}{(n!)^{n+1}}$ is always an integer. And they show how to make $\frac{n!}{n^2}$ into an integer and conclude the problem. But what about the cases where $\frac{n!}{n^2}$ is not an integer, but the product still becomes an integer? For example, $6\cdot\frac{1}{2}=3$. Don't we also have to explore those cases before making the conclusion? Or is there something obvious that I'm missing?
Here's the video explaining exactly that part (start at 12:00).
$\endgroup$ 11 Answer
$\begingroup$You are correct; in the case where $\frac{n!}{n^2}$ is not an integer, you do not know whether or not $\frac{(n^2)!}{(n!)^{n+1}}\cdot\frac{n!}{n^2}$ is an integer. Therefore, for each case such that $\frac{n!}{n^2}$ is not an integer, you need to manually check whether or not $\frac{(n^2)!}{(n!)^{n+1}}\cdot\frac{n!}{n^2}$ is an integer.
There are $16$ exceptional cases where $\frac{n!}{n^2}$ is not an integer; $n=4$, and the $15$ prime numbers between $1$ and $50$. The primes, $p$, are easy to check (just count the factors of $p$ in the numerator and denominator of $\frac{(n^2)!}{(n!)^{n+1}}\cdot\frac{n!}{n^2}$ to see they are not integers), so that just leaves $n=4$. This is all described in solution 1 of your linked solution: .
$\endgroup$ 0
