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?
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
6
$\begingroup$
discrete-mathematics
-
4Clearly, 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
-
0I 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
-
0I didn't say it was an answer, it was a start of an idea. – 2012-11-14
-
0This is why i up voted your previous comment – 2012-11-14
-
0Note 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 3 – 2012-11-14