IMO 1995 SL 24

Problem

S2 (POL)IMO4 The positive real numbers x0, x1, . . . , x1995 satisfy x0 = x1995 and xi−1 + xi−1 = 2xi + 1 xi for i = 1, 2, . . ., 1995. Find the maximum value that x0 can have.

Solution

The given condition is equivalent to (2xi −xi−1)(xixi−1 −1) = 0, so either xi = 1 2xi−1 or xi = xi−1 . We shall show by induction on n that for any n \geq0, xn = 2knxen for some integer kn, where |kn| \leqn and en = (−1)n−kn. Indeed, this is true for n = 0. If it holds for some n, then xn+1 = 1 2xn = 2kn−1xen (hence kn+1 = kn −1 and en+1 = en) or xn+1 = xn = 2−knx−en (hence kn+1 = −kn and en+1 = −en). Thus x0 = x1995 = 2k1995xe1995 . Note that e1995 = 1 is impossible, since in that case k1995 would be odd, although it should equal 0. Therefore e1995 = −1, which gives x2 0 = 2k1995 \leq21994, so the maximal value that x0 can have is 2997. This value is attained in the case xi = 2997−i for i = 0, . . . , 997 and xi = 2i−998 for i = 998, . . ., 1995. Second solution. First we show that there is an n, 0 \leqn \leq1995, such that xn = 1. Suppose the contrary. Then each of xn belongs to one of the intervals I−i−1 = [2−i−1, 2−i) or Ii = (2i, 2i+1], where i = 0, 1, 2, . . .. Let xn \inIin. Note that by the formula for xn, in and in−1 are of different parity. Hence i0 and i1995 are also of different parity, contradicting x0 = x1995. It follows that for some n, xn = 1. Now if n \leq997, then x0 \leq2997, while if n \geq998, we also have x0 = x1995 \leq2997.