For a given integer n≥2, let a0,a1,…,an be integers satisfying 0=a0<a1<…<an=2n−1. We aim to find the smallest possible number of elements in the set {ai+aj∣0≤i≤j≤n}.
First, we prove that the set {ai+aj∣1≤i≤j≤n−1} takes all residues modulo 2n−1. Consider the 2n numbers:
a0<a1<⋯<an−1<an
and
r−a0>r−a1>⋯>r−an−1>r−an
for any integer 0≤r≤2n−2. By the Pigeonhole Principle, there must be two numbers that are congruent modulo 2n−1. Since ai≡aj(mod2n−1) for 1≤i<j≤n−1, there exist 1≤i,j≤n−1 such that ai≡r−aj(mod2n−1), meaning ai+aj≡r(mod2n−1).
Thus, the set {ai+aj∣1≤i≤j≤n−1} takes all residues modulo 2n−1.
Returning to the original problem, we note that there are 2n+1 distinct numbers:
a0+a0<a0+a1<⋯<a0+an−1<an+a0<an+a1<⋯<an+an,
which, modulo 2n−1, take only n different residues. Combining this with the fact that {ai+aj∣1≤i≤j≤n−1} takes all residues modulo 2n−1, there are at least n−1 additional distinct numbers.
Therefore, the number of elements in the set {ai+aj∣0≤i≤j≤n} is at least 2n+1+n−1=3n.
By setting ai=n−1 for 1≤i≤n−1, we achieve ∣{ai+aj∣0≤i≤j≤n}∣=3n. Hence, the smallest possible number of elements in the set is 3n.