Romania — NMO Selection Tests for the Balkan and International Mathematical Olympiads

The required maximum is $k-1$ and is achieved, for instance, at $n = k!$. To complete the proof, we now show that at least one of the $k$ numbers $\frac{1}{n-j}\binom{n}{k}$, $j = 0, 1, \dots, k-1$, is not an integer. To this end, we exhibit a $\mathbb{Z}$-linear combination of these numbers which is not an integer. For instance,
$$\sum_{j=0}^{k-1} (-1)^{k-j-1} \binom{k-1}{j} \cdot \frac{1}{n-j} \binom{n}{k} = \frac{1}{k} \sum_{j=0}^{k-1} \prod_{i \neq j} \frac{n-i}{j-i} = \frac{1}{k}$$
is not an integer, since $k \ge 2$. The leftmost equality above is easily proved by noticing that the polynomial
$$\sum_{j=0}^{k-1} \prod_{i \neq j} \frac{X-i}{j-i}$$
has degree at most $k-1$, and takes on the value 1 at $k$ distinct points, namely, 0, 1, ..., $k-1$, so it is identically 1.