Prueba probabilística argumento

Question

Esto en realidad no es una tarea problema, pero me gustaría ser tratados como si fueran uno. Yo no estoy en busca de una solución, me gustaría tener algunos consejos sobre cómo empezar.

Estoy tratando de resolver el tercer problema aquí. Me las arreglé para resolver los dos primeros, por lo que creo que entiendo lo que probabilística argumento. Permítanme reescribir la pregunta aquí. Me gustaría probar que para cualquier conjunto dado $S \subset \mathbb{Z}\setminus\{0\}$ del tamaño de la $n$, debe haber un par de subconjuntos disjuntos $A$$B$, de tal manera que $|A| + |B| > 2 n / 3$ y el tanto $A$ $B$ son de suma-libre (cada uno no contienen tres elementos donde uno es la suma de los otros dos).

Realmente estoy atascado en averiguar el "derecho" de la variable aleatoria a la vista. Cualquier (no spoiler) consejos son muy apreciados!

Answer 1

Puedo publicar mi comentario como una respuesta ya que la idea funcionó.

Deje $p$ ser un gran primer tales que los elementos de la $S$ son distintos modulo $p$. A continuación, $S$ puede ser considerado como un subconjunto de a $\mathbb Z/p\mathbb Z$. Elija $x \in \{1,\ldots,p-1\}$ uniformemente al azar y considerar el conjunto $xS \subseteq \mathbb Z/p\mathbb Z$. A continuación, encontrará distinto de la suma de la libre subconjuntos $A$ $B$ $\mathbb Z/p\mathbb Z$ y muestran que para algunos la elección de $x$ $2n/3$ elementos de $xS$ caer en $A$ o $B$.