6
$\begingroup$

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?

  • 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$.2012-11-14
  • 0
    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?2012-11-14
  • 0
    I didn't say it was an answer, it was a start of an idea.2012-11-14
  • 0
    This is why i up voted your previous comment2012-11-14
  • 0
    Note that there is also a limit on the number of odd numbers you can have in your set.2012-11-14
  • 0
    @yet_another_student then you divide this set by 3, because it also has to hold (a/3)+(b/3)=(c/3) if a=b=c=0 mod 32012-11-14

1 Answers 1