IMO 1990 SL 26

Origin: USA

Problem

Let P be a cubic polynomial with rational coefficients, and let q1, q2, q3, . . . be a sequence of rational numbers such that qn = P(qn+1) for all n \geq1. Prove that there exists k \geq1 such that for all n \geq1, qn+k = qn.

Solution

We note that |P(x)/x| \to\infty. Hence, there exists an integer number M such that M > |q1| and |P(x)| \leq|x| ⇒|x| < M. It follows that |qi| < M for all i \inN because assuming |qi| \geqM for some i we get |qi−1| = |P(qi)| > |qi| \geqM and this ultimately contradicts |q1| < M. Let us define q1 = r s and P(x) = ax3+bx2+cx+d e where r, s, a, b, c, d, e are all integers. For N = sa we shall prove by induction that Nqi is an integer for all i \inN. By definition N ̸= 0.

For i = 1 this obviously holds. Assume it holds for some i \inN. Then using qi = P(qi+1) we have that Nqi+1 is a zero of the polynomial Q(x) = e aN 3  P  x N

−qi

= x3 + (sb)x2 + (s2ac)x + (s3a2d −s2ae(Nqi)) . Since Q(x) is a monic polynomial with integer coefficients (a conclusion for which we must assume the induction hypothesis) and Nqi+1 is rational it follows by the rational root theorem that Nqi+1 is an integer. It follows that all qi are multiples of 1/N. Since −M < qi < M we conclude that qi can take less than T = 2M|N| distinct values. Therefore for each j there are mj and mj + kj (kj > 0) both belonging to the set {jT + 1, jT + 2, . . . , jT + T } such that qmj = qmj+kj. Since kj < T for all kj it follows that there exists a positive integer k which appears an infinite number of times in the sequence kj, i.e. there exist infinitely many integers m such that qm = qm+k. Moreover, qm = qm+k clearly implies qn = qn+k for all n \leqm. Hence qn = qn+k holds for all n.