IMO 1991

Given any real number a > 1 construct a bounded infinite sequence x₀, x₁, x₂, ... such that |x_n - x_m| |n - m|^a ≥ 1 for every pair of distinct n, m.

[An infinite sequence x₀, x₁, x₂, ... of real numbers is bounded if there is a constant C such that |x_n| < C for all n.]

Solution

By Marcin Mazur, University of Illinois at Urbana-Champaign

Let t = 1/2^a. Define c = 1 - t/(1 - t). Since a > 1, c > 0. Now given any integer n > 0, take the binary expansion n = ∑_i b_i 2ⁱ, and define x_n = 1/c ∑_bi>0 tⁱ. For example, taking n = 21 = 2⁴ + 2² + 2⁰, we have x₂₁ = (t⁴ + t² + t⁰)/c. We show that for any unequal n, m, |x_n - x_m| |n - m|^a ≥ 1. This solves the problem, since the x_n are all positive and bounded by (∑ tⁿ )/c = 1/(1 - 2t).

Take k to be the highest power of 2 dividing both n and m. Then |n - m| ≥ 2^k. Also, in the binary expansions for n and m, the coefficients of 2⁰, 2¹, ... , 2^k-1 agree, but the coefficients for 2^k are different. Hence c |x_n - x_m| = t^k + ∑_i>k y_i, where y_i = 0, tⁱ or - tⁱ. Certainly ∑_i>k y_i > - ∑_i>k tⁱ = t^k+1/(1 - t), so c |x_n - x_m| > t^k(1 - t/(1 - t)) = c t^k. Hence |x_n - x_m| |n - m|^a > t^k 2^ak = 1.

Solutions are also available in   István Reiman, International Mathematical Olympiad 1959-1999, ISBN 189-8855-48-X.

32nd IMO 1991

© John Scholes
jscholes@kalva.demon.co.uk
14 Sep 1999