IMO 1994 SL N4

Origin: FRA | Category: Number Theory

Problem

For any positive integer x0, three sequences {xn}, {yn}, and {zn} are defined as follows: (i) y0 = 4 and z0 = 1; (ii) if xn is even for n \geq0, xn+1 = xn 2 , yn+1 = 2yn, and zn+1 = zn; (iii) if xn is odd for n \geq0, xn+1 = xn −yn 2 −zn, yn+1 = yn, and zn+1 = yn + zn. The integer x0 is said to be good if xn = 0 for some n \geq1. Find the number of good integers less than or equal to 1994.

Solution

Note first that yn = 2k (k \geq2) and zk \equiv1 (mod 4) for all n, so if xn is odd, xn+1 will be even. Further, it is shown by induction on n that yn > zn when xn−1 is even and 2yn > zn > yn when xn−1 is odd. In fact, n = 1 is the trivial case, while if it holds for n \geq1, then yn+1 = 2yn > zn = zn+1 if xn is even, and 2yn+1 = 2yn > yn + zn = zn+1 if xn is odd (since then xn−1 is even). If x1 = 0, then x0 = 3 is good. Suppose xn = 0 for some n \geq2. Then xn−1 is odd and xn−2 is even, so that yn−1 > zn−1. We claim that a pair (yn−1, zn−1), where 2k = yn−1 > zn−1 > 0 and zn−1 \equiv1 (mod 4), uniquely determines x0 = f(yn−1, zn−1). We see that xn−1 = 2yn−1 + zn−1, and define (xk, yk, zk) backwards as follows, until we get (yk, zk) = (4, 1). If yk > zk, then xk−1 must have been even, so we define (xk−1, yk−1, zk−1) = (2xk, yk/2, zk); otherwise xk−1 must have been odd, so we put (xk−1, yk−1, zk−1) = (xk −yk/2 + zk, yk, zk −yk). We even- tually arrive at (y0, z0) = (4, 1) and a good integer x0 = f(yn−1, zn−1), as claimed. Thus for example (yn−1, zn−1) = (64, 61) implies xn−1 = 93, (xn−2, yn−2, zn−2) = (186, 32, 61) etc., and x0 = 1953, while in the case of (yn−1, zn−1) = (128, 1) we get x0 = 2080. Note that y′ > y ⇒f(y′, z′) > f(y, z) and z′ > z ⇒f(y, z′) > f(y, z). Therefore there are no y, z for which 1953 < f(y, z) < 2080. Hence all good integers less than or equal to 1994 are given as f(y, z), y = 2k \leq64 and 0 < z \equiv1 (mod 4), and the number of such (y, z) equals 1+2+4+8+16 = 31. So the answer is 31.