18th Iberoamerican 2003

Pablo was trying to solve the following problem: find the sequence x₀, x₁, x₂, ... , x₂₀₀₃ which satisfies x₀ = 1, 0 ≤ x_i ≤ 2 x_i-1 for 1 ≤ i ≤ 2003 and which maximises S. Unfortunately he could not remember the expression for S, but he knew that it had the form S = ± x₁ ± x₂ ± ... ± x₂₀₀₂ + x₂₀₀₃. Show that he can still solve the problem.

Solution

For any combination of signs the maximum is obtained by taking all x_i as large as possible. Suppose we have a different set of x_i. Then for some k we must have x_k < 2x_k-1 and x_i = 2x_i-1 for all i > k. Suppose 2x^k-1 - x^k = h > 0. Then we can increase x_k by h, x_k+1 by 2h, x_k+2 by 4h, ... . So the sum will be increased by h(± 1 ± 2 ± ... ± 2^m-1 + 2^m) for some m ≥ 0. But ± 1 ± 2 ± ... ± 2^m-1 ≥ -(1 + 2 + ... + 2^m-1) = -2^m + 1, so the overall sum will be increased by at least 1. So the set of x_i was not maximal.

18th Ibero 2003

© John Scholes
jscholes@kalva.demon.co.uk
2 Jan 04
Last corrected 2 Jan 04