IMO 1993 SL 12

Origin: IRE

Problem

Let n, k be positive integers with k \leqn and let S be a set containing n distinct real numbers. Let T be the set of all real numbers of the form x1 + x2 + \cdot \cdot \cdot + xk, where x1, x2, . . . , xk are distinct elements of S. Prove that T contains at least k(n −k) + 1 distinct elements.

Solution

Let x1 < x2 < \cdot \cdot \cdot < xn be the elements of S. We use induction on n. The result is trivial for k = 1 or n = k, so assume that it is true for n −1 numbers. Then there exist m = (k −1)(n −k) + 1 distinct sums of k −1 numbers among x2, . . . , xn; call these sums Si, S1 < S2 < \cdot \cdot \cdot < Sm. Then x1 + S1, x1 + S2, . . . , x1 + Sm are distinct sums of k of the numbers x1, x2, . . . , xn. However, the biggest of these sums is x1 + Sm \leqx1 + xn−k+2 + xn−k+3 + \cdot \cdot \cdot + xn; hence we can find n−k sums that are greater and thus not included here: x2+xn−k+2+\cdot \cdot \cdot+xn, x3+xn−k+2+\cdot \cdot \cdot+xn, . . . , xn−k+1+xn−k+2+\cdot \cdot \cdot+xn. This counts for k(n −k) + 1 sums in total. Remark. Equality occurs if S is an arithmetic progression.