10th Iberoamerican 1995 Problem B3 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).
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 f n (h) ≠ h for n = 1, 2, ... , M-m-1 and f M-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, ... , N 2 , the third block, N 2 +1, ... , N 3 and so on. Then for any integer n we have f m (n) ≠ n for m < kn where k = 1 - 1/N. 10th Ibero 1995 © John Scholes jscholes@kalva.demon.co.uk 21 January 2004 Last corrected/updated 21 January 2004