Past exam of the mathematics course of the University of Cambridge / 2021 / iii / Paper 129 / 1 / b

Starting with $y_1=0$, choose $y_j\in A+A$ for as long asThe union of these translates lies in $X+2A$, whose size is at most $K^2|X|$ by part a. The first translate contributes $|X|$, and every later translate contributes at least $|X|/2$, soLet $Y=\{y_1,\dots ,y_m\}$. Maximality says that, for each $z\in A+A$, more than half of the elements $x\in X$ satisfyfor some $y_i\in Y$. Given $z,z^{\prime }\in A+A$, the two corresponding subsets of $X$ each have more than $|X|/2$ elements, so they intersect. For an $x$ in their intersection there are $x_i,x_j\in X$ and $y_i,y_j\in Y$ such thatSubtracting givesAs every element of $A+A-A-A$ is some $z-z^{\prime }$, this proves