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. ***
Problem
Source: Romania TST 3 2010, Problem 4
Tags: floor function, combinatorics proposed, combinatorics, Cauchy-Davenport theorem
29.08.2012 21:37
We could mimic (with minor changes) the proof of the Cauchy-Davenport theorem which uses the Davenport transform.
31.08.2012 12:29
And here are the details. For $x\in X,\, y\in Y$, from now on $x+y$ will mean $x+y$ modulo $[0,1)$, i.e. $x+y- \lfloor x+y \rfloor $. First we have $X+Y \subset X+2Y $. (Here $2Y$ means $Y+Y$.). It is because $0 \in Y$. Suppose that $Y\setminus \{0\} \neq \emptyset$. Then If we assume that $X+Y = X+2Y$ then $X+Y=X+nY$. This means that if take $y \in Y, \, y\neq 0 \, \Rightarrow \, ny \in X+Y, \forall n \in \mathbb{N}.$ But $ ny \neq 1 $, so $\{ny|\, n \in \mathbb{N} \}$ is infinite, contradicton. Let $Z=(X+2Y)\setminus (X+Y) \neq \emptyset $. If $z\in Z$ define: $Y_z = \{y \in Y|\, z-y \notin X+Y \}$ and $ Y^*_z = \{y \in Y|\, z-y \in X+Y \}$. $Y_z$ is called a Davenport transform of $Y$. Some properties: $Y_z$ and $Y_z^*$ are non empty, e.g. $0 \in Y_z$. $Y_z \cup Y^*_z = Y$. (1) $(X+Y_z) \cup (z-Y^*_z) \subset X+Y $. (2) $(X+Y_z) \cap (z-Y^*_z) = \emptyset $. (1) is clear, (2) is obtained by assuming on the contrary that $\exists x\in X,\, \exists y\in Y_z,\, \exists y^*\in Y^*_z$ so that $x+y=z-y^* \,\Rightarrow \, z-y = x+y^*\Rightarrow y \in Y^*_z $, a contradiction. (1) and (2) yield: $|X+Y| \geq |X+Y_z| + |z-Y^*_z|$ or (3) $|X+Y| \geq |X+Y_z| + |Y|-|Y_z|$ Assume that the problem assertion is not true and there exist $X,\,Y$ such that: (4) $|X+Y| \leq |X|+|Y| - 2$ Then $Y\setminus \{0\} \neq \emptyset$. Choose such pair $X,\, Y$ so that $|Y|$ is minimal. Ussing (3), for some $z\in (X+2Y)\setminus (X+Y)$, we get: $ |X+Y_z| \leq |X+Y|-|Y| + |Y_z| \leq |X|-2+ |Y_z| $ Therefore the pair $(X, Y_z)$ also satisfies (4) and $|Y_z| < |Y|$, which contradics minimality of $|Y|$. More on Cauchy-Davenport's can find here: http://www.folk.uib.no/nmaoy/papers/sumsetsR.pdf