67th NMO Selection Tests for BMO and IMO

Let $S\subseteq \mathbb{Z}/n\mathbb{Z}$ be a set whose pairwise sums of unordered pairs are distinct, and consider the pairwise differences of ordered pairs. The crucial observation is that if a difference $d\ne 0$ occurs twice in $S$, then these two occurrences must be adjacent in a 3-term arithmetic progression in $S$ (with difference $d$). Indeed, if $a,a+d,a^{\prime },a^{\prime }+d$ are all in $S$, where $a\ne a^{\prime }$, then $a+(a^{\prime }+d)=a^{\prime }+(a+d)$ so, by assumption on $S$, $a^{\prime }=a\pm d$, i.e. the ordered pairs $(a,a+d)$ and $(a^{\prime },a^{\prime }+d)$ are adjacent in a 3-term arithmetic progression. We also observe that, excepting the arithmetic progression of common difference $n/2$, in case $n$ is even, no two 3-term arithmetic progressions can have the same central term, since if $a,a\pm d,a\pm d^{\prime }$ are all in $S$, where $d,d^{\prime }\ne 0,n/2$ are distinct, then $(a+d^{\prime })+(a-d^{\prime })=(a+d)+(a-d)$ would violate the assumption on $S$. It follows that the number of 3-term arithmetic progressions in $S$ is at most $|S|+2$. Now any non-zero difference not occurring in a 3-term arithmetic progression can appear at most once in $S$, and those which do appear in 3-term arithmetic progressions can appear at most twice, except $\pm n/3$ in case $n$ is divisible by 3, which can appear three times. Consequently, the total number of non-zero differences appearing in $S$ is at least $|S|(|S|-1)-(|S|+2)-2=|S{|}^2-2|S|-4$. If $|S|>1+\sqrt{n+4}$, this quantity is greater than $n-1$ — a contradiction.