South African Mathematics Olympiad

$$(2n)!=(\genfrac{}{}{0ex}{}{2n}{n})\cdot n{!}^2\equiv (\genfrac{}{}{0ex}{}{2n}{n})\cdot (-a{)}^2\mathrm{mod}(n!+a),$$ so if $n!+a$ divides $(2n)!$, then it also divides $a^2\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$. We will show that when $n$ is large, $n!+a$ is greater than $a^2\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$ and therefore does not divide it (unless $a=0$). Assume in the following that $a\ne 0$ and $n>\frac{4^5}{12}{a}^2$. First of all, by the binomial theorem, $$\left(\genfrac{}{}{0ex}{}{2n}{n}\right)\le \sum _{k=0}^{2n}\left(\genfrac{}{}{0ex}{}{2n}{k}\right)=2^{2n}=4^n.$$ If $a>0$, we have $$0<\frac{a^2}{n!+a}\left(\genfrac{}{}{0ex}{}{2n}{n}\right)<\frac{a^2}{n!}\left(\genfrac{}{}{0ex}{}{2n}{n}\right)\le \frac{a^2}{n!}{4}^n=\left(\frac{4^{n-5}}{5\cdot 6\cdots (n-1)}\right)\frac{4^5{a}^2}{24n}<1.$$ If $a<0$, then we observe that $n!>n>2|a|$, so that $$0<\frac{a^2}{n!+a}\left(\genfrac{}{}{0ex}{}{2n}{n}\right)=\frac{a^2}{n!-|a|}\left(\genfrac{}{}{0ex}{}{2n}{n}\right)<\frac{a^2}{\frac{1}{2}n!}\left(\genfrac{}{}{0ex}{}{2n}{n}\right)\le \frac{2a^2}{n!}{4}^n=\left(\frac{4^{n-5}}{5\cdot 6\cdots (n-1)}\right)\frac{4^5{a}^2}{12n}<1.$$

Thus $\frac{a^2\left(\genfrac{}{}{0ex}{}{2n}{n}\right)}{n!+a}$ is not an integer for all such $n$, which contradicts our assumption that $n!+a$ divides $(2n)!$ (and thus $a^2\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$) for infinitely many $n$. So $a=0$ is the only possibility (and indeed $n!$ divides $(2n)!$ for all $n$).

---

Alternative solution.

We show that $n!+a$ cannot divide $(2n)!$ if $a\ne 0$, $n\ge 2|a|$ and $n\ge 9$. In this case, $\frac{n!}{a}$ is an integer. If $n!+a$ divides $(2n)!$, then so does $\frac{n!}{a}+1$. Next note that every prime $p\le n$ divides $\frac{n!}{a}$: if $p\nmid a$, this is obvious (since $p\nmid n!$), and if $p\mid a$, then we see that $p$ divides $2|a|$, which occurs as a factor of $\frac{n!}{a}$. In either case, we find that $\frac{n!}{a}+1$ is not divisible by $p$. So $\frac{n!}{a}+1$ does not have any prime factors $\le n$, which means that it is coprime to all numbers $\le n$ as well as all the even numbers $\le 2n$. Therefore $\frac{n!}{a}+1$ must divide the product of all odd numbers greater than $n$ and less than $2n$. By our assumption, $\left|\frac{n!}{a}+1\right|\ge \frac{n}{a}\cdot (n-1)!-1\ge 2(n-1)!-1$. We show that the product of the odd numbers between $n$ and $2n$ is less than $2(n-1)!-1$ for $n\ge 9$, which yields the desired contradiction. For $n=9$ and $n=10$, we have the two inequalities $$2\cdot 8!-1=80639>36465=11\cdot 13\cdot 15\cdot 17$$ and $$2\cdot 9!-1=725759>692835=11\cdot 13\cdot 15\cdot 17\cdot 19$$ respectively. Now we proceed by induction. Assume that $$2(n-1)!-1>\prod _{\begin{array}{c}n<k<2n\\ k\text{ odd}\end{array}}k.$$ If $n>10$ is even, we use the induction hypothesis to obtain $$\begin{gathered} \prod _{\begin{array}{c}n<k<2n\\ k\text{ odd}\end{array}}k=\frac{(2n-3)(2n-1)}{n-1}\prod _{\begin{array}{c}n-2<k<2n-4\\ k\text{ odd}\end{array}}k<2(2n-1)\prod _{\begin{array}{c}n-2<k<2n-4\\ k\text{ odd}\end{array}}k<(4n-2)(2(n-3)!-1) \\ <(n-1)(n-2)(2(n-3)!-1)=2(n-1)!-(n-1)(n-2)<2(n-1)!-1, \end{gathered}$$ and if $n>10$ is odd, we get analogously $$\begin{gathered} \prod _{\begin{array}{c}n<k<2n\\ k\text{ odd}\end{array}}k=\frac{(2n-3)(2n-1)}{n}\prod _{\begin{array}{c}n-2<k<2n-4\\ k\text{ odd}\end{array}}k<2(2n-3)\prod _{\begin{array}{c}n-2<k<2n-4\\ k\text{ odd}\end{array}}k<(4n-6)(2(n-3)!-1) \\ <(n-1)(n-2)(2(n-3)!-1)=2(n-1)!-(n-1)(n-2)<2(n-1)!-1. \end{gathered}$$

This completes the induction and thus the proof.