ELMO 2019 Problem 1

Let $P(x)$ be a polynomial with integer coefficients such that $P(0)=1$ , and let $c > 1$ be an integer. Define $x_0=0$ and $x_{i+1} = P(x_i)$ for all integers $i \ge 0$ . Show that there are infinitely many positive integers $n$ such that $\gcd (x_n, n+c)=1$ .

Proposed by Milan Haiman and Carl Schildkraut