# In any set of n different natural numbers, exists subset of more than n/3 numbers, such as there are no three numbers in it : a+b=c

I need to prove, that in any set of n different natural numbers, exists subset of more than n/3 numbers, such as there are no three numbers in it, one of which is the sum of two others. Can anyone help me with this?

-
Clearly, the subset of $n\equiv 1\pmod 3$ is strictly not closed additively, as is the subset of $n\equiv 2\pmod 3$. So for this property to fail, more than $n/3$ of the numbers have to be divisible by $3$. – Thomas Andrews Nov 14 '12 at 20:26
I don't understand something. It's obvious, that if all our numbers are $\equiv 1\pmod 3$ or $\equiv 2\pmod 3$, than we can find such a subset. But what if there are more than n/3 numbers divisible by 3? – yet_another_student Nov 14 '12 at 20:49
I didn't say it was an answer, it was a start of an idea. – Thomas Andrews Nov 14 '12 at 20:51
This is why i up voted your previous comment – Amr Nov 14 '12 at 20:52
Note that there is also a limit on the number of odd numbers you can have in your set. – Mark Bennet Nov 14 '12 at 21:01

I think this probablistic argument should work: Let $S$ be our set of size $n$. Pick some very large prime $p$ or the form $p = 3k+2$ (this is possible by Dirichlet's theorem on prime numbers in arithmetic progressions). We can assume $p > \max S$, so that we can consider $S$ as a subset of $\mathbb Z/p\mathbb Z$. Now choose an $x \in (\mathbb Z/p\mathbb Z)^\times$ uniformly at random and consider $xS \subseteq \mathbb Z/p \mathbb Z$. Note that the set $A = \{k+1,\ldots,2k+1\} \subset \mathbb Z/p\mathbb Z$ is sum-free modulo $p$ and contains $k+1$ numbers. The probability that for a particular number $s \in S$ the number $xs$ falls into $A$ is $\frac{k+1}{3k+2} > \frac{1}{3}$. By linearity of expectation, the set $xS$ contains on average $\frac{k+1}{3k+2}n$ elements in $A$. That means there has to be at least one choice of $x$ such that $xS \cap A$ has size at least $\frac{k+1}{3k+2}n > n/3$. Then $S \cap x^{-1}A$ is a subset of $S$ which is sum-free (modulo $p$, hence also as a subset of $\mathbb N$), and has size $> n/3$.