IMO 2012 Shortlist A6

Category: Algebra

Problem

Let f : N → N be a function, and let fm be f applied m times. Suppose that for every n ∈ N there exists a k ∈ N such that f2k (n) = n + k, and let kn be the smallest such k. Prove that the sequence k1,k2,... is unbounded. Solution. We restrict attention to the set S = {1,f(1),f2 (1),...}. Observe that S is unbounded because for every number n in S there exists a k > 0 such that f2k (n) = n + k is in S. Clearly f maps S into itself; moreover f is injective on S. Indeed if fi (1) = fj (1) with i 6= j then the values fm (1) start repeating periodically from some point on, and S would be finite. Define g : S → S by g(n) = f2kn (n) = n + kn. We prove that g is injective too. Suppose that g(a) = g(b) with a < b. Then a + ka = f2ka (a) = f2kb(b) = b + kb implies ka > kb. So, since f is injective on S, we obtain f2(ka−kb) (a) = b = a + (ka − kb). However this contradicts the minimality of ka as 0 < ka − kb < ka. Let T be the set of elements of S that are not of the form g(n) with n ∈ S. Note that 1 ∈ T by g(n) > n for n ∈ S, so T is non-empty. For each t ∈ T denote Ct = {t,g(t),g2 (t),...}; call Ct the chain starting at t. Observe that distinct chains are disjoint because g is injective. Each n ∈ S\T has the form n = g(n′ ) with n′ < n, n′ ∈ S. Repeated applications of the same observation show that n ∈ Ct for some t ∈ T, i. e. S is the disjoint union of the chains Ct. If fn (1) is in the chain Ct starting at t = fnt (1) then n = nt + 2a1 + ··· + 2aj with fn (1) = gj (fnt (1)) = f2aj (f2aj−1 (···f2a1 (fnt (1)))) = fnt (1) + a1 + ··· + aj. Hence fn (1) = fnt (1) + n − nt = t + n − nt . (1) Now we show that T is infinite. We argue by contradiction. Suppose that there are only finitely many chains Ct1,...,Ctr , starting at t1 < ··· < tr. Fix N. If fn (1) with 1 ≤ n ≤ N is in Ct then fn (1) = t + n−nt ≤ tr + N by (1). But then the N + 1 distinct natural numbers 1,f(1),...,fN (1) are all less than tr + N and hence N +1 ≤ tr + N . This is a contradiction if N is sufficiently large, and hence T is infinite. To complete the argument, choose any k in N and consider the k +1 chains starting at the first k + 1 numbers in T. Let t be the greatest one among these numbers. Then each of the chains in question contains a number not exceeding t, and at least one of them does not contain any number among t+1,...,t+k. So there is a number n in this chain such that g(n)−n > k, i. e. kn > k. In conclusion k1,k2,... is unbounded.17