RO-NMO 2007 Problem 104

a) For a finite set of natural numbers $S$ , denote by $S+S$ the set of numbers $z=x+y$ , where $x,y\in S$ . Let $m=|S|$ . Show that $|S+S|\leq \frac{m(m+1)}{2}$ .

b) Let $m$ be a fixed positive integer. Denote by $C(m)$ the greatest integer $k\geq 1$ for which there exists a set $S$ of $m$ integers, such that $\{1,2,\ldots,k\}\subseteq S\cup(S+S)$ . For example, $C(3)=8$ , with $S=\{1,3,4\}$ . Show that $\frac{m(m+6)}{4}\leq C(m) \leq \frac{m(m+3)}{2}$ .