En cualquier conjunto de n diferentes números naturales, existe subconjunto de más de n/3 números, como no hay tres números : a+b=c

Question

Tengo que probar, que en cualquier conjunto de n diferentes números naturales, existe subconjunto de más de n/3 números, como no hay tres números, uno de los cuales es la suma de los otros dos. Alguien me puede ayudar con esto?

Answer 1

Creo que este probablistic argumento debería funcionar: Vamos a $S$ ser nuestro conjunto de tamaño $n$. Recoger algunas muy grandes prime $p$ o el $p = 3k+2$ (esto es posible a través del teorema de Dirichlet sobre primos en progresiones aritméticas). Podemos suponer $p > \max S$, así que podemos considerar $S$ como un subconjunto de a $\mathbb Z/p\mathbb Z$. Ahora elija un $x \in (\mathbb Z/p\mathbb Z)^\times$ uniformemente al azar y se considerar $xS \subseteq \mathbb Z/p \mathbb Z$. Tenga en cuenta que el conjunto de $A = \{k+1,\ldots,2k+1\} \subset \mathbb Z/p\mathbb Z$ es de suma-libre modulo $p$ y contiene $k+1$ números. La probabilidad de que para un determinado número de $s \in S$ el número de $xs$ cae en $A$$\frac{k+1}{3k+2} > \frac{1}{3}$. Por la linealidad de la expectativa, el conjunto de $xS$ contiene, en promedio, $\frac{k+1}{3k+2}n$ elementos en $A$. Eso significa que tiene que haber al menos una selección de $x$ tal que $xS \cap A$ tiene un tamaño de al menos $\frac{k+1}{3k+2}n > n/3$. A continuación, $S \cap x^{-1}A$ es un subconjunto de a $S$ lo cual es de suma-libre (modulo $p$, por lo tanto, también como un subconjunto de a $\mathbb N$), y tiene el tamaño de $> n/3$.