Putnam 2001, Problem B-4

Let $S$ denote the set of rational numbers different from $\{-1, 0, 1\}$. Define $f : S \to S$ by $f(x) = x - 1/x$. Prove or disprove that
$$\bigcap_{n=1}^{\infty} f^{(n)}(S) = \emptyset,$$
where $f^{(n)}$ denotes $f$ composed with itself $n$ times.

Solution:
For a rational number $p/q$ expressed in lowest terms, define its height $H(p/q)$ to be $|p| + |q|$. Then for any $p/q \in S$ expressed in lowest terms, we have $H(f(p/q)) = |q^2 - p^2| + |pq|$; since by assumption $p$ and $q$ are nonzero integers with $|p| \neq |q|$, we have
$$H(f(p/q)) - H(p/q) = |q^2 - p^2| + |pq| - |p| - |q|$$
$$\geq 3 + |pq| - |p| - |q|$$
$$= (|p| - 1)(|q| - 1) + 2 \geq 2.$$

It follows that $f^{(n)}(S)$ consists solely of numbers of height strictly larger than $2n + 2$, and hence
$$\bigcap_{n=1}^\infty f^{(n)}(S) = \emptyset.$$

Note: many choices for the height function are possible: one can take $H(p/q) = \max{|p|,|q|}$, or $H(p/q)$ equal to the total number of prime factors of $p$ and $q$, and so on. The key properties of the height function are that on one hand, there are only finitely many rationals with height below any finite bound, and on the other hand, the height function is a sufficiently "algebraic" function of its argument that one can relate the heights of $p/q$ and $f(p/q)$.