IMO 1994 SL A2

Let m and n be positive integers. The set A = {a1, a2, . . . ,

imoshortlistmathematicsolympiadalgebra

IMO 1994 SL A2

Origin: FRA | Category: Algebra

Problem

Let m and n be positive integers. The set A = {a1, a2, . . . , am} is a subset of {1, 2, . . . , n}. Whenever ai + aj \leqn, 1 \leqi \leqj \leqm, ai + aj also belongs to A. Prove that a1 + a2 + \cdot \cdot \cdot + am m \geqn + 1 .

Solution

We may assume that a1 > a2 > \cdot \cdot \cdot > am. We claim that for i = 1, . . . , m, ai +am+1−i \geqn+1. Indeed, otherwise ai+am+1−i, . . . , ai+am−1, ai+am are i different elements of A greater than ai, which is impossible. Now by adding for i = 1, . . . , m we obtain 2(a1 + \cdot \cdot \cdot + am) \geqm(n + 1), and the result follows.