NMO Selection Tests for the Balkan and International Mathematical Olympiads

Let $S(X,Y)=\{x+y-\lfloor x+y\rfloor :x\in X\text{ and }y\in Y\}$ and proceed by induction on $|Y|$.

If $|Y|=1$, the statement is clear.

Assume henceforth $|Y|>1$ and let $y_0\in Y$, $y_0\ne 0$. The conditions $y_0\ne 0$ and $x+y_0=1$ for no $x\in X$ imply that $0\notin S(X,y_0)$. Since $0\in X$, and $X$ and $S(X,y_0)$ have the same cardinality, there are elements that lie in $S(X,y_0)$ but not in $X$; that is, $x_0+y_0-\lfloor x_0+y_0\rfloor$ for some $x_0\in X$.

Let $$Y_0=\{y:y\in Y\text{ and }{x}_0+y-\lfloor x_0+y\rfloor \notin X\}$$ and $$X_0=\{x_0+y-\lfloor x_0+y\rfloor :y\in Y_0\}.$$ Clearly, $0\notin Y_0$, $X_0$ and $Y_0$ are both non-empty and have the same cardinality, so $0<|X_0|=|Y_0|<|Y|$.

Let further $X^{\prime }=X\cup X_0$ (notice that this is a disjoint union) and $Y^{\prime }=Y\setminus Y_0$, so $X$ is a proper non-empty subset of $X^{\prime }$, $Y^{\prime }$ is a proper non-empty subset of $Y$, and $$|X^{\prime }|+|Y^{\prime }|=|X|+|X_0|+|Y|-|Y_0|=|X|+|Y|.(\ast )$$ Obviously, $X^{\prime }$ and $Y^{\prime }$ both contain $0$ and we now show that $S(X^{\prime },Y^{\prime })\subseteq S(X,Y)$ and $x^{\prime }+y^{\prime }=1$ for no $x^{\prime }\in X^{\prime }$ and no $y^{\prime }\in Y^{\prime }$.

Clearly, we need consider only the case $x^{\prime }\in X_0$; that is, $x^{\prime }=x_0+y-\lfloor x_0+y\rfloor$ for some $y\in Y_0$. Thus, if $y^{\prime }\in Y^{\prime }$, then $$\begin{array}{rl}{x}^{\prime }+y^{\prime }-\lfloor x^{\prime }+y^{\prime }\rfloor & =x_0+y-\lfloor x_0+y\rfloor +y^{\prime }-\lfloor x_0+y-\lfloor x_0+y\rfloor +y^{\prime }\rfloor \\ & =x_0+y+y^{\prime }-\lfloor x_0+y+y^{\prime }\rfloor \\ & =(x_0+y^{\prime }-\lfloor x_0+y^{\prime }\rfloor )+y-\lfloor (x_0+y^{\prime }-\lfloor x_0+y^{\prime }\rfloor )+y\rfloor .\end{array}$$ Notice that $x_0+y^{\prime }-\lfloor x_0+y^{\prime }\rfloor \in X$, by the definition of $Y^{\prime }$, to infer that $x^{\prime }+y^{\prime }-\lfloor x^{\prime }+y^{\prime }\rfloor \in S(X,Y_0)\subseteq S(X,Y)$, and thereby $S(X^{\prime },Y^{\prime })\subseteq S(X,Y)$.

Finally, write $$\begin{array}{rl}{x}^{\prime }+y^{\prime }& =x_0+y-\lfloor x_0+y\rfloor +y^{\prime }\\ & =(x_0+y^{\prime }-\lfloor x_0+y^{\prime }\rfloor )+y-\lfloor x_0+y\rfloor +\lfloor x_0+y^{\prime }\rfloor ,\end{array}$$ recall that $x_0+y^{\prime }-\lfloor x_0+y^{\prime }\rfloor \in X$ and consider the possible values of $\lfloor x_0+y\rfloor$ and $\lfloor x_0+y^{\prime }\rfloor$ to conclude that $x^{\prime }+y^{\prime }\ne 1$.

Consequently, $$\begin{array}{rlrl}|S(X,Y)|& \ge |S(X^{\prime },Y^{\prime })|& & \text{for }S(X^{\prime },Y^{\prime })\subseteq S(X,Y)\\ & \ge |X^{\prime }|+|Y^{\prime }|-1& & \text{by the induction hypothesis}\\ & =|X|+|Y|-1.& & \text{by }(\ast )\end{array}$$