Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
4  
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
show 1 more comment

1 Answer

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$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.