MathDB
Covered by translates of A-A

Source: Romania TST 1 2009, Problem 1

May 4, 2012
combinatorics proposedcombinatorics

Problem Statement

For non-empty subsets A,BZA,B \subset \mathbb{Z} define A+B={a+b:aA,bB}, AB={ab:aA,bB}.A+B=\{a+b:a\in A, b\in B\},\ A-B=\{a-b:a\in A, b\in B\}.
In the sequel we work with non-empty finite subsets of Z\mathbb{Z}.
Prove that we can cover BB by at most A+BA\frac{|A+B|}{|A|} translates of AAA-A, i.e. there exists XZX\subset Z with XA+BA|X|\leq \frac{|A+B|}{|A|} such that BxX(x+(AA))=X+AA.B\subseteq \cup_{x\in X} (x+(A-A))=X+A-A.