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?
Tell me more
×
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 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$. |
||||
|
|
