Iranian Mathematical Olympiad

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(\mathrm{mod}2)$ and $P_i(jk+\frac{1}{2})<0$ if $j\not\equiv n(\mathrm{mod}2)$.

Now let $Q(x)=P_{i_1}(x)+P_{i_2}(x)+\cdots +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$