MathDB

T contains at least k(n-k)+1 distinct elements

Source: IMO Shortlist 1993, Ireland 2

March 15, 2006

combinatoricsIMO ShortlistAdditive combinatoricsAdditive Number Theory

Problem Statement

Let

n,k \in \mathbb{Z}^{+}

with

k \leq n

and let

S

be a set containing

n

distinct real numbers. Let

T

be a set of all real numbers of the form

x_1 + x_2 + \ldots + x_k

where

x_1, x_2, \ldots, x_k

are distinct elements of

S.

Prove that

T

contains at least

k(n-k)+1

distinct elements.