Iranian Mathematical Olympiad

By induction, we prove $a_n = \frac{2n^n}{n!}$. The base is clear, if the hypothesis holds true for $n$, we have
$$a_{n+1} = \left(1 + \frac{1}{n}\right)^n a_n = 2 \cdot \left(\frac{n+1}{n}\right)^n \frac{n^n}{n!} = 2 \cdot \frac{(n+1)^n}{n!} = 2 \cdot \frac{(n+1)^{n+1}}{(n+1)!},$$
now we have:
$$\begin{aligned} \frac{a_n a_{n-1} \cdots a_1}{n+1} &= \frac{2^n}{n+1} \frac{n^n \cdot (n-1)^{n-1} \cdots 2^2 1^1}{n! (n-1)! \cdots 2! 1!} \\ &= \frac{2^n}{n+1} \cdot \frac{n(n-1)}{1! \cdot 2!} \cdots \frac{n(n-1) \cdots (n-k-1)}{k!} \cdots \frac{n!}{n!} \\ &= \frac{2^n}{n+1} \binom{n}{0} \binom{n}{1} \cdots \binom{n}{n-1} \binom{n}{n}, \end{aligned}$$
note that if $n$ is odd, then
$$\binom{n}{0} \binom{n}{1} \cdots \binom{n}{n-1} \binom{n}{n} = \binom{n}{0} \binom{n}{1} \cdots \binom{n}{\frac{n-1}{2}},$$
is a perfect square. So it is enough to choose an odd $n$ such that $\frac{2^n}{n+1}$ is a perfect square. For this, we set $n = 2^k - 1$ for an odd $k$, then $\frac{2^n}{n+1} = 2^{2^k-k-1}$ is a perfect square as desired.

As in the first solution, we have
$$\frac{a_n a_{n-1} \cdots a_1}{n+1} = \frac{2^n}{n+1} \frac{n^n \cdot (n-1)^{n-1} \cdots 2^2 1^1}{n! (n-1)! \cdots 2! 1!} = \frac{2^n}{n+1} A_n$$
Each natural number $1 \le i \le n$ is repeated $n-i+1$ times in the denominator of $A_n$. In the numerator of $A_n$ $i$ appears with the power $i$ so we can write
$$A_n = \prod i^{2i-n-1}$$
which means that if $n$ is odd and $A_n$ is natural then it is a perfect square. So it is enough to prove that for infinitely many odd $n$, $A_n$ is a natural number. Assume that $\nu_p(n) = k$, then we have
$$\nu_p(A) = \sum_{j=1}^{k} 2p^j(1 + 2 + \cdots + \lfloor \frac{n}{p^j} \rfloor) - (n+1) \sum_{j=1}^{k} k \lfloor \frac{n}{p^j} \rfloor$$
We want to show that $\nu_p(A)$ is non-negative. For $1 \le j \le K$ we have to show that
$$\begin{align*} 2p^j(1 + 2 + \cdots + \lfloor \frac{n}{p^j} \rfloor) &\ge (n+1)\lfloor \frac{n}{p^j} \rfloor \\ \iff p^j \lfloor \frac{n}{p^j} \rfloor (\lfloor \frac{n}{p^j} \rfloor + 1) &\ge (n+1) \frac{n}{p^j} \\ \iff p^j (\lfloor \frac{n}{p^j} \rfloor + 1) &\ge (n+1) \end{align*}$$
By division algorithm, $n = p^j q + r$ for $0 \le r < p^j$. Hence we have to show that $p^j(q+1) \ge p^j q + r + 1 \Leftrightarrow p^j \ge r + 1$ which is clear. The rest of the proof would be analogous to the first solution. ■