Maths Olympiad Prep

Library / /1 of 5

Algebra Difficulty 5.6 AIME, harder Prove it Brazil

Let cc be a rational. Let f(x)=x2+cf(x) = x^2 + c. Define f(0)(x)=xf^{(0)}(x) = x, f(n+1)(x)=f(f(n)(x))f^{(n+1)}(x) = f(f^{(n)}(x)). Show that there are only finitely many rationals xx such that the sequence f(0)(x),f(1)(x),f(2)(x),f^{(0)}(x), f^{(1)}(x), f^{(2)}(x), \dots takes only finitely many values.

Solution

For sake of simplicity, call xx a periodic number if f(0)(x)f^{(0)}(x), f(1)(x)f^{(1)}(x), f(2)(x)f^{(2)}(x), \dots takes finitely many values.

If x>c+1|x| > |c| + 1 then x2x=x(x1)>(c+1)cc    x2c>xx^2 - |x| = |x|(|x| - 1) > (|c| + 1)|c| \ge |c| \implies x^2 - |c| > |x|, so f(x)=x2+cx2c>x|f(x)| = |x^2 + c| \ge x^2 - |c| > |x|, that is, f(n+1)(x)>f(n)(x)>>x|f^{(n+1)}(x)| > |f^{(n)}(x)| > \dots > |x| and f(0)(x)f^{(0)}(x), f(1)(x)f^{(1)}(x), f(2)(x)f^{(2)}(x), \dots takes infinitely many values. So if xx is periodic then xc+1|x| \le |c| + 1, that is, all periodic numbers lie in the interval [(c+1),c+1][-(|c| + 1), |c| + 1].

Let c=rsc = \frac{r}{s}, x=yzx = \frac{y}{z} and f(x)=uvf(x) = \frac{u}{v}, gcd(r,s)=gcd(y,z)=gcd(u,v)=1\gcd(r, s) = \gcd(y, z) = \gcd(u, v) = 1, s,z,v>0s, z, v > 0. So
uv=(yz)2+rs    y2sv=z2(usrv) \frac{u}{v} = \left(\frac{y}{z}\right)^2 + \frac{r}{s} \iff y^2 s v = z^2 (u s - r v)
Since gcd(y,z)=1\gcd(y, z) = 1, z2z^2 divides svs v, so svz2    vz2ss v \ge z^2 \iff v \ge \frac{z^2}{s}. If z2s>z    z>s\frac{z^2}{s} > z \iff z > s then the denominator of xx is less than the denominator of f(x)f(x) and consequently the denominator of f(n)(x)f^{(n)}(x) is less than the denominator f(n+1)(x)f^{(n+1)}(x), so xx is not a periodic point.

So all rational periodic points of ff lie in the interval [(c+1),c+1][-(|c|+1), |c|+1] and have denominator not greater than the denominator of cc. Thus the number of rational periodic points of ff is finite.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.