IMO 1990 SL 18

Origin: NOR

Problem

Let a, b be natural numbers with 1 \leqa \leqb, and M = / a+b . Define the function f : Z \toZ by f(n) = . n + a, if n < M, n −b, if n \geqM. Let f 1(n) = f(n), f i+1(n) = f(f i(n)), i = 1, 2, . . . . Find the smallest natural number k such that f k(0) = 0.

Solution

Clearly, it suffices to consider the case (a, b) = 1. Let S be the set of integers such that M −b \leqx \leqM + a −1. Then f(S) \subseteqS and 0 \inS. Consequently, f k(0) \inS. Let us assume for k > 0 that f k(0) = 0. Since f(m) = m + a or f(m) = m −b, it follows that k can be written as k = r + s, where ra −sb = 0. Since a and b are relatively prime, it follows that k \geqa + b. Let us now prove that f a+b(0) = 0. In this case a + b = r + s and hence f a+b(0) = (a + b −s)a −sb = (a + b)(a −s). Since a + b | f a+b(0) and f a+b(0) \inS, it follows that f a+b(0) = 0. Thus for (a, b) = 1 it follows that k = a + b. For other a and b we have k = a+b (a,b).