IMO 2002 SL A2

Origin: YUG | Category: Algebra

Problem

Let a1, a2, . . . be an infinite sequence of real numbers for which there exists a real number c with 0 \leqai \leqc for all i such that |ai −aj| \geq i + j for all i, j with i ̸= j. Prove that c \geq1.

Solution

For n \geq2, let (k1, k2, . . . , kn) be the permutation of {1, 2, ..., n} with ak1 \leqak2 \leq\cdot \cdot \cdot \leqakn. Then from the condition of the problem, using the Cauchy–Schwarz inequality, we obtain

c \geqakn −ak1 = |akn −akn−1| + \cdot \cdot \cdot + |ak3 −ak2| + |ak2 −ak1| \geq k1 + k2 + k2 + k3

• \cdot \cdot \cdot + kn−1 + kn \geq (n −1)2 (k1 + k2) + (k2 + k3) + \cdot \cdot \cdot + (kn−1 + kn) = (n −1)2 2(k1 + k2 + \cdot \cdot \cdot + kn) −k1 −kn \geq (n −1)2 n2 + n −3 \geqn −1 n + 2. Therefore c \geq1 − n+2 for every positive integer n. But if c < 1, this inequality is obviously false for all n > 1−c −2. We conclude that c \geq1. Remark. The least value of c is not greater than 2 ln 2. An example of a sequence {an} with 0 \leqan \leq2 ln 2 can be constructed inductively as follows: Given a1, a2, . . . , an−1, then an can be any number from [0, 2 ln 2] that does not belong to any of the intervals  ai − i+n, ai + i+n

(i = 1, 2, . . . , n −1), and the total length of these intervals is always less than or equal to n + 1 + n + 2 + \cdot \cdot \cdot + 2n −1 < 2 ln 2.