Greece — Selection Examination

We can write: $A = \frac{4n!}{n!\ 2n!} = \binom{3n}{n} \cdot 3n+1\ 3n+2\ \dots\ 4n-1 \cdot 4n \in \mathbb{Z}$, since $\binom{3n}{n} \in \mathbb{Z}$.

Next we observe that in the prime factorization of $n!$ the exponent of $2$ is
$$\exp n = \left\lfloor \frac{n}{2} \right\rfloor + \left\lfloor \frac{n}{2^2} \right\rfloor + \dots + \left\lfloor \frac{n}{2^m} \right\rfloor, \qquad (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} + \dots + \frac{n}{2^m} = \frac{n}{2} \left( 1 + \frac{1}{2} + \dots + \frac{1}{2^{m-1}} \right) = n - \frac{n}{2^m}. \qquad (3)$$
Similarly we find that:
$$\exp 2n = \left\lfloor \frac{2n}{2} \right\rfloor + \left\lfloor \frac{2n}{4} \right\rfloor + \dots + \left\lfloor \frac{2n}{2^{m+1}} \right\rfloor = n + \left\lfloor \frac{n}{2} \right\rfloor + \left\lfloor \frac{n}{2^2} \right\rfloor + \dots + \left\lfloor \frac{n}{2^m} \right\rfloor = n + \exp n \qquad (4)$$
$$\begin{aligned} \exp 4n &= \left\lfloor \frac{4n}{2} \right\rfloor + \left\lfloor \frac{4n}{2^2} \right\rfloor + \left\lfloor \frac{4n}{2^3} \right\rfloor + \dots + \left\lfloor \frac{4n}{2^{m+2}} \right\rfloor \\ &= 2n + n + \left\lfloor \frac{n}{2} \right\rfloor + \left\lfloor \frac{n}{2^2} \right\rfloor + \dots + \left\lfloor \frac{n}{2^m} \right\rfloor = 3n + \exp n \end{aligned}$$
Therefore the exponent of $2$ in the factorization of $A$ is
$$\begin{aligned} & 3n + \exp n - \left[ \exp n + n + \exp n \right] = 2n - \exp n \\ & \geq 2n - \left( n - \frac{n}{2^m} \right) = n + \frac{n}{2^m} \geq n + 1, \end{aligned}$$
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!} = \binom{2n-1}{n-1}$, we can write
$$A = 2^{n+1} \binom{2n-1}{n-1} \cdot (2n+1)(2n+3)\dots(4n-1),$$
and hence $A$ is integer divided by $2^{n+1}$.