No sum of three numbers equals another number in set Consider the set $S=\{1,2,\ldots,1000\}$. What is the maximum size of a subset $S'$ such that for any distinct $a,b,c,d\in S'$, we have $a+b+c\neq d$?
We can choose $S'=\{333,334,335,\ldots,1000\}$, so that $|S'|=668$. For the proof that this is optimal, I would like to use the pigeonhole principle to show that any $669$ elements will have $a+b+c=d$. But choosing the buckets iteratively like $\{1,2,3,6\},\{4,5,7,16\},\ldots$ seems difficult.
 A: Suppose $|S|=669$ and let $A=S \cap [1,332],\ B=S \cap [333,1000].$ Further define the set of "gaps" as $G=[333,1000] \setminus B,$ which are entries not in $S$ but in the range $[333,1000].$ Since $|[333,1000]|=668$ we have 
$$|G|=668-|B|=668-(669-|A|)=|A|-1,$$
i.e. the number of gaps is one less than the number of low numbers (elements of $A$).
Now if $|A|=1,$ say $A=\{x\},$ then there are no gaps, and since $x+333+334 \le 332+333+334=999,$ we have a contradiction, i.e. a case of $a+b+c=d.$
If $|A|=2,$ say $A=\{x,y\},$ then $x+y \le 331+332=663,$ and in this case there is one gap, so that one of the sums $x+y+333\le 996,\ x+y+334\le 997$ will produce a sum $a+b+c=d,$ that is, if $333$ is a gap we can use $x+y+334.$
Otherwise $|A| =k \ge 3$ and we list the elements of $A$ in (strictly) increasing order as $a_1, a_2, \ldots a_k.$  For each $j$ we have the upper bound $a_j \le 332+j-k,$ there being $k-j$ elements of $A$ to the right of $a_j.$ We will be considering the two element sets $T$ in the ordered list
$$\{a_1,a_2\},\ \{a_1,a_3\},\cdots, \{a_1,a_k\}, \\
\{a_2,a_k\},\ \{a_3,a_k\}, \cdots, \{a_{k-1},a_k\}.\tag{1}$$
There are $2k-3$ sets in this list, and their sums are in strictly increasing order since the $a_j$ are in order. Note that since $k\ge 3$ we have $2k-3 \ge k$ sets in the list to work with.
The idea now is to form three element set using the sets $T$ together with the least element of $B$. Suppose the least element of $B$ is $y=333+r.$ Then there are $r$ gaps in $G$ lying to the left of $y$ which have been used up, and since $|G|=k-1$ there remain $k-1-r$ gaps in $G$ which lie to the right of $y.$ So we proceed to use the least $k-r$ of the sets $T$, each along with $y$, and then since there is at least one more set than there are remaining gaps to the right of $y,$ there will be at least one $T$ such that the sum of $T$ with $y$ does not end up being a gap, i.e. lies in the set $S$, provided we show the bound that for each $T$ we use the proposed sum of three terms is less than $1000.$ 
The sums of the $T$ are in increasing order.  So the greatest of these, provided we use as suggested above the least $k-r$ of them, is the sum for the $(k-r)$th term in the list $(1)$, which provided $r>0$ comes from the first line of $(1),$ namely from the pair $\{a_1,a_{k-r+1}\}$ with sum at most $(332+1-k)+(332+(k-r+1)-k)=666-r-k.$ In this case when added to $y=333+r$ the sum is at most $999-k \le 1000.$ On the other hand, if $r=0$ then the $(k-r)$th i.e. $k$th term in the list is the first term of row $(2)$ of $(1),$ so is the pair $\{a_2,a_k\}$ with sum at most $(332+2-k)+(332+k-k)=666-k,$ and then adding $y=333+r=333+0$ [keeping in mind this is the case $r=0$] we arrive again at a total sum of at most $999-k \le 1000.$
A: Here's an easier approach that is distinct from Coffeemath's.
Suppose we have 669 elements, arranged in increasing order:
$$ 1 \leq a_ 1 < a_2 < \ldots < a_{669}  \leq 1000 $$
Note that $a_1 \leq 1000 - 669 + 1 = 332$
Consider the 2 sequences of 667 terms each, with $ n \geq 3$
$$ b_n = a_n + a _1 , c_n = a_n - a_2$$
There are $ 2 \times 667 = 1334$ terms in these 2 sequences.
Their potential values range from $1$ to $ 332 + 1000 = 1332$.          Since $1334 > 1332$, hence by the Pigeonhole Principle, there exist 2 terms that are equal.
Clearly, terms in each sequence are distinct, so we must have some $ b_i = c_j$.
If $i = j$ then $ a_i + a_1 = a_i - a_2$ which is a contradiction.
So $ i \neq j$, which gives us $a_i + a_1 + a_2 = a_j $.
Note: The conclusion that $a_i + a_1 + a_2 = a_j $ seems very surprising to me, since it's not clear how we could prove it more directly.
