f is a function defined on the positive integers with positive integer values. Use f m(n) to mean f(f( ... f(n) ....)) = n where f is taken m times, so that f 2(n) = f(f(n)), for example. Find the largest possible 0 < k < 1 such that for some function f, we have f m(n) ≠ n for m = 1, 2, ... , [kn], but f m(n) = n for some m (which may depend on n).
Answer
we can get k arbitrarily close to 1
Solution
The basic idea is to take a block of integers m+1, m+2, ... , M and to define f(m+1) = m+2, f(m+2) = m+3, ... , f(M-1) = M, f(M) = m+1. Then for any integer h in the block we have fn(h) ≠ h for n = 1, 2, ... , M-m-1 and fM-m(h) = h. Note that the ratio (M-m)/h is worst (smallest) for h = M.
For example, take the first block to be 1, 2, ... , N, the second block to be N+1, ... , N2, the third block, N2+1, ... , N3 and so on. Then for any integer n we have fm(n) ≠ n for m < kn where k = 1 - 1/N.
© John Scholes
jscholes@kalva.demon.co.uk
21 January 2004
Last corrected/updated 21 January 2004