IMO 1992 SL 14

Origin: POL

Problem

For any positive integer x define g(x) = greatest odd divisor of x, f(x) = . x/2 + x/g(x), if x is even; 2(x+1)/2, if x is odd. Construct the sequence x1 = 1, xn+1 = f(xn). Show that the number 1992 appears in this sequence, determine the least n such that xn = 1992, and determine whether n is unique.

Solution

We see that x1 = 20. Suppose that for some m, r \inN we have xm = 2r. Then inductively xm+i = 2r−i(2i + 1) for i = 1, 2, . . ., r and xm+r+1 = 2r+1. Since every natural number can be uniquely represented as the prod- uct of an odd number and a power of two, we conclude that every natural number occurs in our sequence exactly once. Moreover, it follows that 2k −1 = xk(k+1)/2. Thus xn = 1992 = 23 \cdot 249 implies that xn+3 = 255 = 2\cdot128−1 = x128\cdot129/2 = x8256. Hence n = 8253.