XIX OBM

Let $a_1<a_2<\cdots <a_n$ be the elements of $A$. The diameter of $A$ is $d(A)=a_n-a_1$. The minimum and maximum of $A+A=\{x+y\mid x,y\in A\}$ are $a_1+a_1$ and $a_n+a_n$. Since $A+A$ has $\frac{n(n+1)}{2}$ elements, $2a_n-2a_1+1\ge \frac{n(n+1)}{2}⟺d(A)\ge \frac{n^2}{4}+\frac{n-2}{4}\ge \frac{n^2}{4}$.

To prove the upper bound, we need to construct a set $A$ with property $P$ such that $d(A)<n^3$. We do this recursively. Start with $A=\{0,1\}$ and we will adjoin elements to $A$. Suppose we already have $a_1=0<a_2=1<\cdots <a_n$ in $A$ such that $\{a_1,a_2,\dots ,a_n\}$ has property $P$. Adjoining $a_{n+1}$ will generate $n+1$ more sums: $a_1+a_{n+1},a_2+a_{n+1},\dots ,a_{n+1}+a_{n+1}$. All these sums must be different from any $a_i+a_j$, $1\le i\le j\le n$. Moreover, $a_{n+1}$ must be different from all numbers $a_i$, $1\le i\le n$. This means that $a_{n+1}\notin \{a_i+a_j-a_k\mid 1\le i\le j\le k\}\cup \left\{\frac{a_i+a_j}{2}\mid 1\le i,j\le n\right\}=B$. This set has no more than $n^3+\frac{n(n+1)}{2}$ elements. So we may choose $a_{n+1}$ as the smaller number not in $B$, and so $a_{n+1}\le n^3+\frac{n(n+1)}{2}<(n+1{)}^3$. Thus $d(A)=a_{n+1}-a_1=a_{n+1}<(n+1{)}^3$.

Now we are going to prove the “bonus” part of the problem. Let $p$ be a prime and consider $A=\{k+2p\cdot (k^2\mathrm{mod}p)\mid 0\le k\le p-1\}$. We have $d(A)\le (p-1)+2p(p-1)=2p^2-p-1<2p^2$. Moreover, $r+2p(r^2\mathrm{mod}p)+$ $s+2p(s^2\mathrm{mod}p)=t+2p(t^2\mathrm{mod}p)+u+2p(u^2\mathrm{mod}p)⟺r+s=t+u$ and $r^2\mathrm{mod}p+s^2\mathrm{mod}p=t^2\mathrm{mod}p+u^2\mathrm{mod}p$. So $r-t=u-s$ and $r^2-t^2\equiv u^2-s^2(\mathrm{mod}p)⟺(r-t)(r+t)\equiv (u-s)(u+s)(\mathrm{mod}p)$ $⟺r-t\equiv u-s\equiv 0(\mathrm{mod}p)$ or $r+t\equiv u+s(\mathrm{mod}p)$, hence $r=t$ and $s=u$ or $r=u$ and $s=t$.