MathDB

Addition of subsets

Source: China Mathematical Olympiad 2014 Q6

December 22, 2013

pigeonhole principleceiling functioncombinatorics proposedcombinatorics

Problem Statement

For non-empty number sets

2S=\{2s\mid s\in S\}

, define the sets

S+T=\{s+t\mid s\in S, t\in T\}

and

2S=\{2s\mid s\in S\}

. Let

D+D\subseteq 2(A+B)

be a positive integer, and

A, B

be two non-empty subsets of

\{1,2\ldots,n\}

. Show that there exists a subset

D

of

A+B

such that 1)

D+D\subseteq 2(A+B)

, 2)

|D|\geq\frac{|A|\cdot|B|}{2n}

, where

|X|

is the number of elements of the finite set

X

.

Back to Problems View on AoPS