IMO 1995/B1 solution

IMO 1995

Problem B1

Find the maximum value of x₀ for which there exists a sequence x₀, x₁, ... , x₁₉₉₅ of positive reals with x₀ = x₁₉₉₅ such that for i = 1, ... , 1995:

x_i-1 + 2/x_i-1 = 2x_i + 1/x_i.

Answer

2⁹⁹⁷.

Solution

The relation given is a quadratic in x_i, so it has two solutions, and by inspection these are x_i = 1/x_i-1 and x_i-1/2. For an even number of moves we can start with an arbitrary x₀ and get back to it. Use n-1 halvings, then take the inverse, that gets to 2^n-1/x₀ after n moves. Repeating brings you back to x₀ after 2n moves. However, 1995 is odd!

The sequence given above brings us back to x₀ after n moves, provided that x₀ = 2^(n-1)/2. We show that this is the largest possible x₀. Suppose we have a halvings followed by an inverse followed by b halvings followed by an inverse. Then if the number of inverses is odd we end up with 2^{a-b+c- ...}/x₀, and if it is even we end up with x₀/2^{a-b+c- ...}. In the first case, since the final number is x₀ we must have x₀ = 2^(a-b+-...)/2. All the a, b, ... are non-negative and sum to the number of moves less the number of inverses, so we clearly maximise x₀ by taking a single inverse and a = n-1. In the second case, we must have 2^{a-b+c- ...} = 1 and hence a - b + c - ... = 0. But that implies that a + b + c + ... is even and hence the total number of moves is even, which it is not. So we must have an odd number of inverses and the maximum value of x₀ is 2^(n-1)/2.

36th IMO 1995