Problem 1466

For each $1 \le i \le k$ we define
$$P_i(x) = (x - i)(x - (k + i))\cdots(x - ((n - 1)k + i)).$$
We claim that these polynomials satisfy the problem condition.
For each $1 \le i \le k$ and each $0 \le j \le n - 1$, $P_i(x)$ has exactly one simple root in the interval $(jk + \frac{1}{2}, (j+1)k + \frac{1}{2})$ so invoking the mean value theorem we deduce that $P_i(jk + \frac{1}{2})$ and $P_i((j+1)k + \frac{1}{2})$ have different signs. Note that $P_i(nk + \frac{1}{2}) > 0$ because $P_i$ is monic and so is positive for large positive values and does not have any root greater than $n$. Thus for each $1 \le i \le k$, $P_i(jk + \frac{1}{2}) > 0$ if $j \equiv n \pmod 2$ and $P_i(jk + \frac{1}{2}) < 0$ if $j \not\equiv n \pmod 2$.

Now let $Q(x) = P_{i_1}(x) + P_{i_2}(x) + \dots + P_{i_t}(x)$ where $i_1, i_2, \dots, i_t \in \{1, 2, \dots, k\}$ are distinct. Obviously $Q(x) \in \mathbb{Z}[x]$ is a polynomial of degree $n$.
For each $0 \le j \le n-1$, numbers $Q(jk + \frac{1}{2})$ and $Q((j+1)k + \frac{1}{2})$ have different signs
because $P_{i_1}, P_{i_2}, \dots, P_{i_t}$ have this property. So again according to mean value theorem
we deduce that $Q$ has a root in the interval $(jk + \frac{1}{2}, (j+1)k + \frac{1}{2})$ and $Q(x)$ has at
most $n$ real roots so all its roots are real, hence the claim is proved. $\square$