Let X be the set of rationals excluding 0, ±1. Let f: X → X be defined as f(x) = x - 1/x. Let f1(x) = f(x), f2(x) = f(f(x)), f3(x) = f(f2(x)) etc. Does there exist a value x in X such that for any positive integer n, we can find y in X with fn(y) = x?
The basic idea is to notice that m/n - n/m = (m2 - n2)/(mn) and that mn is greater than n. So as we iterate f the denominators increase without limit.
There are a few details. Assume that m, n are relatively prime. Then so are (m2 - n2) and mn, so the denominator of f(m/n) is mn. Clearly if m > 1, then mn ≥ 2n. If m = 1, then we have f(1/n) = (1 - n2)/n, which has numerator > 2 (since in this case n cannot be ±1). So for k > 1, the denominator of fk+1(y) is at least double that of fk(y). In particular, it is at least 2k. So given any rational x, take 2k-1 larger than its denominator and we cannot have fk(y) = x for any y.
62nd Putnam 2001
© John Scholes
16 Dec 2001