Past exam of the mathematics course of the University of Cambridge / 2012 / iii / Paper 82 / 3 / Solution

Use the density form of the Szemerédi theorem: for fixed $\alpha >0$ and length $r$, every sufficiently large subset of $\{1,\dots ,N\}$ of size at least $\alpha N$ contains a nonconstant arithmetic progression of length $r$, as established in Szemerédi's density theorem. This theorem supplies a progression, not the desired averaging configuration; we now select the actual indices.

Take $r=2k+1$. Write the resulting progression asand put $y=a+kd\in A$. If $k=2m$ is even, select $y-d,y+d,\dots ,y-md,y+md$. These are $2m=k$ distinct members of the progression, and each opposite pair sums to $2y$. If $k=2m+1$ is odd, select those $2m$ opposite points together with $y$ itself. All $k$ selected points are distinct, and their sum is again $ky$. The case $k=1$ simply selects $y$.

In both cases the indices stay between $0$ and $2k$ and the difference $d$ is nonzero. Thus the precise answer isNo deletion of diagonal solutions and no multidimensional density theorem is needed. The averaging point is allowed to be one of the selected points, as it is in the odd case.