Bulgarian Mathematical Competitions

Solution:
1. We shall use the following well-known facts.

LEMMA 1. For any integer $x$ and any positive integer $t$ the number $t!$ divides $(x+1)(x+2) \ldots (x+t)$.

Proof. The statement is obvious for $x \in \{0, -1, -2, \ldots, -t\}$. We have to prove it for $x > 0$. Let $p$ be a prime divisor of $t$. Then the power of $p$ in the prime factorization of $t!$ is $\left[\frac{t}{p}\right] + \left[\frac{t}{p^{2}}\right] + \cdots$. This power does not exceed the power of $p$ in the prime factorization of $(x+1)(x+2) \ldots (x+t) = \frac{(x+t)!}{x!}$ since the last power equals $\left[\frac{x+t}{p}\right] + \left[\frac{x+t}{p^{2}}\right] + \cdots - \left[\frac{x}{p}\right] - \left[\frac{x}{p^{2}}\right] - \cdots = \left[\frac{x+t}{p}\right] - \left[\frac{x}{p}\right] + \left[\frac{x+t}{p^{2}}\right] - \left[\frac{x}{p^{2}}\right] - \cdots$ and $[a+b] \geq [a] + **$.

LEMMA 2. For $g(x) \in \mathbb{R}[x]$ with $\deg g = n$ one has that $g(\mathbb{Z}) \subset \mathbb{Z}$ if and only if $g(x) = \sum_{i=0}^{n} b_{i} \binom{x}{i}$, where $b_{0}, b_{1}, \ldots, b_{n} \in \mathbb{Z}$.

Proof. Obviously, if $g$ has the above form, then $g(\mathbb{Z}) \subset \mathbb{Z}$.
Conversely, let $g(\mathbb{Z}) \subset \mathbb{Z}$. Set $g(i) = \alpha_{i} \in \mathbb{Z},\ i = 0, 1, \ldots, n$ and apply the Lagrange interpolation formula with knots $0, 1, \ldots, n$. Then
$$\begin{aligned} g(x) & = \sum_{i=1}^{n} \frac{x(x-1) \ldots (x-i+1)(x-i-1) \ldots (x-n) \alpha_{i}}{i(i-1) \ldots (i-(i-1))(i-(i+1)) \ldots (i-n)} \\ & = \sum_{i=1}^{n} (-1)^{n+i} \frac{\alpha_{i} (n+1) \binom{x}{n+1}}{x-i} \end{aligned}$$
It remains to use that any polynomial
$$\frac{(n+1) \binom{x}{n+1}}{x-i} = \frac{x(x-1) \ldots (x-i+1)(x-i+1) \ldots (x-n)}{n!}$$
can be written in the given form (compare the respective coefficients). The lemma is proved.

Let now $m$ be a divisor of $n!$ and consider the polynomial $f(x) = (x+1)(x+2) \ldots (x+n)$. It follows by Lemma 1 that $m$ divides $f(k)$ for any $k \in \mathbb{Z}$. Moreover, $f$ is a monic polynomial (i.e., the leading coefficient of $f$ equals $1$) and hence $\gcd(a_{0}, a_{1}, \ldots, a_{n}, m) = 1$. So all divisors of $n!$ are solutions of the problem.

Assume that $m$ does not divide $n!$ and $m$ is a solution of the problem. Set $r = \frac{m}{(m, n!)}$. It is clear that $r > 1$ is an integer and $(r, n!) = 1$. Let $f(x) = a_{0} + a_{1} x + \cdots + a_{n} x^{n},\ a_{n} \neq 0$, be a polynomial with the desired properties. Then for $g(x) = \frac{f(x)}{r}$ one has that $g(\mathbb{Z}) \subset \mathbb{Z}$ and, by Lemma 2, $g(x) = \sum_{i=0}^{n} b_{i} \binom{x}{i}$, where $b_{0}, b_{1}, \ldots, b_{n} \in \mathbb{Z}$.

Hence $f(x) = \sum_{i=0}^{n} m b_{i} \binom{x}{i}$ and using that $(r, i!) = 1$ for $i = 0, 1, \ldots, n$, we get that $r$ divides all the coefficients of $f$, a contradiction.