MathDB

Additive combinatorics (re Cauchy-Davenport)

Source: Romania TST 3 2010, Problem 4

August 25, 2012

floor functioncombinatorics proposedcombinatoricsCauchy-Davenport theorem

Problem Statement

Let

X

and

Y

be two finite subsets of the half-open interval

[0, 1)

such that

0 \in X \cap Y

and

x + y = 1

for no

x \in X

and no

y \in Y

. Prove that the set

\{x + y - \lfloor x + y \rfloor : x \in X \textrm{ and } y \in Y\}

has at least

|X| + |Y| - 1

elements.
***