IMO 1999 SL C4

Origin: GBR | Category: Combinatorics

Problem

Let A be a set of N residues (mod N 2). Prove that there exists a set B of N residues (mod N 2) such that the set A + B = {a + b | a \inA, b \inB} contains at least half of all residues (mod N 2).

Solution

Let S = {0, 1, . . ., N 2 −1} be the group of residues (with respect to addition modulo N 2) and A an n-element subset. We will use |X| to denote the number of elements of a subset X of S, and X to refer to the complement of X in S. For i \inS we also define Ai = {a + i | a \inA}. Our task is to select 0 \leqi1 < \cdot \cdot \cdot < iN \leqN 2 −1 such that %N j=1 Aij \geq1 2|S|. Each x \inS appears in exactly N sets Ai. We have

 i1<\cdot\cdot\cdot<iN

N G j=1 Aij

=  i1<\cdot\cdot\cdot<iN |{x \inS | x /\inAi1, . . . , AiN }|

 x\inS |{i1 < \cdot \cdot \cdot < iN|x /\inAi1, . . . , AiN }|

 x\inS N 2 −N N 

N 2 −N N  |S| . Hence  i1<\cdot\cdot\cdot<iN

N j=1 Aij

=  i1<\cdot\cdot\cdot<iN ⎛ ⎝|S| −

N G j=1 Aij

⎞ ⎠

N 2 N  − N 2 −N N  |S|. Thus, by the pigeonhole principle, one can choose i1 < \cdot \cdot \cdot < iN such that

%N j=1 Aij \geq  1 −
N 2−N N  /
N 2 N  |S|. Since
N 2 N  /
N 2−N N  \geq  N 2 N 2−N N

 1 + N−1 N

e > 2, it follows that

%N j=1 Aij \geq1 2|S|; hence the cho- sen i1 < \cdot \cdot \cdot < iN are indeed the elements of B that satisfy the conditions of the problem.