Is it smallest or largest? If we want to find the smallest number of elements, that seems too easy.

http://www.artofproblemsolving.com/Forum/viewtopic.php?f=41&t=401136

Can someone post a solution the link above doesn’t work for me

yunxiu wrote: http://www.artofproblemsolving.com/Forum/viewtopic.php?f=41&t=401136 that link corrected : here according to instructions here

Solution 我们先证明 $\{a_i+a_j\mid 1\leq i\leq j\leq n-1\}$ 取遍模 $2n-1$ 完系. 对于所有整数 $0\leq r\leq 2n-2$, 考虑 $2n$ 个数 $$a_0<a_1<\cdots <a_{n-1}<a_{n};$$$$r-a_0>r-a_1>\cdots >r-a_{n-1}>r-a_{n}.$$由抽屉原理, 必有两数模 $2n-1$ 同余. 又对 $\forall 1\leq i<j\leq n-1$, $a_i\not\equiv a_j\pmod {2n-1}$, 因此存在 $1\leq i,j\leq n-1,a_i\equiv r-a_j\pmod{2n-1}$, 即 $a_i+a_j\equiv r\pmod{2n-1}$. 故 $\{a_i+a_j\mid 1\leq i\leq j\leq n-1\}$ 取遍模 $2n-1$ 完系, 结论成立. 回到原题, 注意到有 $2n+1$ 个互不相同的数 $$a_0+a_0<a_0+a_1<\cdots <a_0+a_{n-1}<a_n+a_0<a_n+a_1<\cdots <a_n+a_n,$$且在模 $2n-1$ 下只取遍了 ${n}$ 种不同余数. 结合 $\{a_i+a_j\mid 1\leq i\leq j\leq n-1\}$ 取遍模 $2n-1$ 完系, 还至少有 $n-1$ 个不同的数出现. 因此 $\left|\{ a_i+a_j \mid 0\le i \le j \le n \}\right|\geqslant 2n+1+n-1=3n$. 由对 $\forall 1\leq i\leq n-1$, 取 $a_i=n-1$, 得到 $\left|\{ a_i+a_j \mid 0\le i \le j \le n \}\right|=3n$, 故可取等. 综上所述, 所求最小值为 $\boxed{3n}.\blacksquare$

The answer is $3n$. We claim that $K:=\{ a_i+a_j \mid 0\le i \le j \le n \}$ has at least $3n$ elements. Lemma: Suppose the sequence $\{x_j\}_{j=0}^m$ of integers satisfies $0=x_0<x_1<\dots<x_m$, and $x_j\leq 2j-1$ for $1\leq j\leq m$, then $\{x_i+x_j|0\leq i,j\leq m\}$ contains $\{0,1,\dots,2m\}$. Proof of the lemma: Almost trivial. $\blacksquare$ Induct on $n$. It is easy to check the case $n=1,2,3$. Suppose $n\geq 4$ and the claim is true for $1\leq k<n$. Set $b_j:=a_j-2j$, then $b_0=0$ and $b_n=-1$. Notice that $b_{j+1}-b_j\geq -1$. Therefore one of the two following cases must occur: Case 1: There exists some index $1\leq j\leq n-2$, such that $b_j=0, b_{j+1}=-1$; Case 2: There exists some index $0\leq j \leq n-1,$ such that $b_l\leq -1$ for $1\leq l\leq j$, and $b_l\geq 0$ for $j+1\leq l\leq n-1$. In Case 1, we can use the inductive hypothesis on $a_0,\dots,a_{j+1}$ and $a_j-2j,\dots, a_n-2j$, this would give us $3n+3$ elements from $K$, only the 3 elements $a_j+a_j,a_j+a_{j+1},a_{j+1}+a_{j+1}$ are counted twice, thus $K$ has at least $3n$ elements. In Case 2, use the lemma on $a_0,\dots , a_j$ and $2n-1-a_n,\dots, 2n-1-a_{j+1}$, we conclude that $X=\{0,1,\dots,2j\}\cup\{2n+2j,\dots,4n-2\}$ is contained in $K$. Also $Y=\{a_{j+1},\dots,a_n\}\cup\{2n-1+a_1,\dots,2n-1+a_j\}$ is a subset of $K$. Note that $X$ and $Y$ have empty intersection, and $|X|=2n, |Y|=n$, then $K$ has at least $3n$ elements. Thus we conclude that $|K|\geq 3n$. Take $a_0=0,a_1=2,\dots, a_{n-1}=2n-2,a_{n}=2n-1$, $|K|=3n$. Done! Remark: This solution is way more complicated than the official solution, but I just feel like this is more intuitive and natural.

Claimed Answer: $3n$ Construction: $A = {0,1,...,n-1,2n-1}$; all sums from $0$ to $2n-2$ are attained from the first $n$ elements, and $2n-1$ generates $2n-1$ to $3n-2$, and $4n-2$. Bound: WLOG the min is $0$ and the max is $2n-1$. Claim: if $\geq t+1$ elements are at most $2t-1$, $2t-1$ is an attainable sum. The same holds for $2t$. Proof: There are $t$ disjoint pairs summing to $2t-1$, and at most $t-1$ pairs lose at least one element, so some pair still sums to $2t-1$. The same argument applies to $2t$ given the additional $(t,t)$ pair. Consider the set of all $t \leq 2n-2$ such that there are at least $\lceil \frac{t}{2} \rceil+1$ elements at most $t$. Group these into consecutive intervals, and note that intervals start at an even value (because the requirement for $2t$ doesn't change from $2t-1$ but we can get one more element) but end at even values too (because $2t+1$ has a higher requirement). Let our intervals be $I_1,I_2,...,I_k$, and the in-between intervals be $J_1,J_2,...,J_k$. We can sligtly perturb the intervals as follows; make the left ends open and the right ends closed (so they are all disjoint). Let $|I|$ be the length of interval $I$. We can now see that $|I_i|$ is the number of elements of $I_i$ attainable by definition. Note that $2n-2$ is the endpoint of the last interval, and it necessarily is an ENDPOINT even for a $J$, because $\geq n$ elements are at most $2n-2$. All $J$ intervals can be seen to necessarily end at some element of our set. Claim: $\geq |\frac{J_i}{2}|$ elements in each $J_i$ are attainable by $A+A$ Proof: Let $J_i = (2j_1,2j_2]$. We see that $j_1+1$ elements are part of $A$ that are at most $2j_1$, and that $j_2+1$ elements are part of $A$ that are at most $2j_2$, so there are $j_2-j_1$ elements in this interval. Since each element itself is a sum (due to $0$ being in $A$), this implies the desired claim. Thus, we have at least $\sum{|I_i|}+\frac{1}{2} \sum{|J_i|}$ elements in $(0,2n-1)$ that can be expressed as a sum. We will apply the same argument to the $2n-1$ end for the $(2n-1,4n-2)$ interval. However, it is easy to see due to having $n+1$ elements that each $I_i$ becomes a $J$ interval, and each $J_i$ becomes an $I$ interval here! (the parity imbalance between $2n-1$ and $0$ is important here; we do need to shift our actual interval values over left by $1$ but lengths don't get affected) This gives us at least $\sum{|J_i|}+\frac{1}{2} \sum{|I_i|}$, for an overall total of $\geq \frac{3}{2}(\sum{|I_i|}+\sum{|J_i|}) = 3n-3$ elements expressible as a sum that are not $0,2n-1,4n-2$. As these three are trivially expressible too though, we have at least $3n$ elements expressible, as desired. Q.E.D. This was motivated by failed attempts at considering odd and even values separately (as ${0,2,...,2n-2,2n-1}$ is an equality case too, and is very similar to the ${0,2,...,2n-2,2n}$ set that only has $|A+A|$ equal to $2n+1$); considering small versus large sums separately instead works better, and the parity of $2n-1$ still has a role.

OTIS Formulation wrote: Let $n$ be a positive integer. Over all sets $A$ of $n + 1$ integers satisfying $\max A \: - \: \min \: A = 2n-1$, determine the smallest possible value of $|A + A|$. The answer is $3n$. WLOG that $\min A = 0$ and $\max A = 2n-1$. Construction: Consider $A=\{0, 1, 2, \dots, n-1, 2n-1\}$, and note that \[ A+A = \{0, 1, 2, \dots, 3n-2, 4n-2\} \]has size $3n$. Bound: First, we claim the following: Claim: Each residue modulo $2n-1$ has a representative in $A+A$. Proof. Let $r$ be an arbitrary residue modulo $2n-1$. We claim that $r-A$ and $A$ modulo $2n-1$ are never disjoint, which suffices. This is clear as both sets modulo $2n-1$ each have size $n$, from which $|r-A|+|A|>|\mathbb{Z}_{2n-1}|$. We will show that at least $n+1$ residues modulo $2n-1$ appear twice in $A+A$. For each $x \in A$, note that both $x$ and $x+\max A=x+(2n-1)$ are in $A+A$. By size, none of the sets $\{x, x+(2n-1)\}$ for $x \in A$ overlap. Thus, $A+A$ contains one element corresponding to each residue modulo $2n-1$, and one additional element for $n+1$ of the residues, so $A+A$ has size at least $(2n-1)+(n+1)=3n$, as desired.

thanosaops wrote: Claim: $\geq |\frac{J_i}{2}|$ elements in each $J_i$ are attainable by $A+A$ Proof: Let $J_i = (2j_1,2j_2]$. We see that $j_1+1$ elements are part of $A$ that are at most $2j_1$, and that $j_2+1$ elements are part of $A$ that are at most $2j_2$, so there are $j_2-j_1$ elements in this interval. Since each element itself is a sum (due to $0$ being in $A$), this implies the desired claim. This does not seem to work; It might be the case that there's $j_{i+1}$ integers in $[0, 2j_i)$ in which case both conditions are satisfied but there's no integers in $J_i$. The ideas do look similar to ChanadlerBong's solution so I might be mistaken / this might be patchable.