SELECTION EXAMINATION

We can write: $A=\frac{4n!}{n!2n!}=\left(\genfrac{}{}{0ex}{}{3n}{n}\right)\cdot 3n+13n+2\dots 4n-1\cdot 4n\in \mathbb{Z}$, since $\left(\genfrac{}{}{0ex}{}{3n}{n}\right)\in \mathbb{Z}$.

Next we observe that in the prime factorization of $n!$ the exponent of $2$ is $$\exp n=\lfloor \frac{n}{2}\rfloor +\lfloor \frac{n}{2^2}\rfloor +\cdots +\lfloor \frac{n}{2^m}\rfloor ,(2)$$ where $m$ is the maximal natural number satisfying the inequality $2^m\le n$. Hence $$\exp n\le \frac{n}{2}+\frac{n}{2^2}+\cdots +\frac{n}{2^m}=\frac{n}{2}\left(1+\frac{1}{2}+\cdots +\frac{1}{2^{m-1}}\right)=n-\frac{n}{2^m}.(3)$$ Similarly we find that: $$\exp 2n=\lfloor \frac{2n}{2}\rfloor +\lfloor \frac{2n}{4}\rfloor +\cdots +\lfloor \frac{2n}{2^{m+1}}\rfloor =n+\lfloor \frac{n}{2}\rfloor +\lfloor \frac{n}{2^2}\rfloor +\cdots +\lfloor \frac{n}{2^m}\rfloor =n+\exp n(4)$$ $$\begin{array}{rl}\exp 4n& =\lfloor \frac{4n}{2}\rfloor +\lfloor \frac{4n}{2^2}\rfloor +\lfloor \frac{4n}{2^3}\rfloor +\cdots +\lfloor \frac{4n}{2^{m+2}}\rfloor \\ & =2n+n+\lfloor \frac{n}{2}\rfloor +\lfloor \frac{n}{2^2}\rfloor +\cdots +\lfloor \frac{n}{2^m}\rfloor =3n+\exp n\end{array}$$ Therefore the exponent of $2$ in the factorization of $A$ is $$\begin{array}{rl}& 3n+\exp n-\left[\exp n+n+\exp n\right]=2n-\exp n\\ & \ge 2n-\left(n-\frac{n}{2^m}\right)=n+\frac{n}{2^m}\ge n+1,\end{array}$$ that is $2^{n+1}$ is a factor of $A$.

(Second solution)

We can write $A=\frac{(2n+1)(2n+2)\dots (4n-1)(4n)}{n!}$. We observe that in the numerator we have $n-1$ even integers, from $2n+2$ till $4n-2$, that is we get $2$ as a factor $n-1$ times. Moreover from $4n$, we get the factor $2$ two times and hence $$A=2^{n+1}\frac{n(n+1)(n+2)\dots (2n-1)}{n!}\cdot (2n+1)(2n+3)\dots (4n-1)$$ Since $\frac{n(n+1)(n+2)\dots (2n-1)}{n!}=\left(\genfrac{}{}{0ex}{}{2n-1}{n-1}\right)$, we can write $$A=2^{n+1}\left(\genfrac{}{}{0ex}{}{2n-1}{n-1}\right)\cdot (2n+1)(2n+3)\dots (4n-1),$$ and hence $A$ is integer divided by $2^{n+1}$.