Ninguna suma de tres números es igual a otro número del conjunto

Question

Considere el conjunto $S=\{1,2,\ldots,1000\}$ . ¿Cuál es el tamaño máximo de un subconjunto $S'$ tal que para cualquier $a,b,c,d\in S'$ tenemos $a+b+c\neq d$ ?

Podemos elegir $S'=\{333,334,335,\ldots,1000\}$ para que $|S'|=668$ . Para demostrar que esto es óptimo, me gustaría utilizar el principio de encasillamiento para mostrar que cualquier $669$ los elementos tendrán $a+b+c=d$ . Pero elegir los cubos de forma iterativa como $\{1,2,3,6\},\{4,5,7,16\},\ldots$ parece difícil.

Answer 1

Supongamos que $|S|=669$ y que $A=S \cap [1,332],\ B=S \cap [333,1000].$ Defina además el conjunto de "huecos" como $G=[333,1000] \setminus B,$ que son entradas que no están en $S$ pero en el rango $[333,1000].$ Desde $|[333,1000]|=668$ tenemos $$|G|=668-|B|=668-(669-|A|)=|A|-1,$$ es decir, el número de huecos es uno menos que el número de números bajos (elementos de $A$ ).

Ahora bien, si $|A|=1,$ diga $A=\{x\},$ entonces no hay huecos, y como $x+333+334 \le 332+333+334=999,$ tenemos una contradicción, es decir, un caso de $a+b+c=d.$

Si $|A|=2,$ diga $A=\{x,y\},$ entonces $x+y \le 331+332=663,$ y en este caso hay un hueco, por lo que una de las sumas $x+y+333\le 996,\ x+y+334\le 997$ producirá una suma $a+b+c=d,$ es decir, si $333$ es un hueco que podemos utilizar $x+y+334.$

De lo contrario, $|A| =k \ge 3$ y enumeramos los elementos de $A$ en orden (estrictamente) creciente como $a_1, a_2, \ldots a_k.$ Para cada $j$ tenemos el límite superior $a_j \le 332+j-k,$ habiendo $k-j$ elementos de $A$ a la derecha de $a_j.$ Consideraremos los dos conjuntos de elementos $T$ en la lista ordenada $$\{a_1,a_2\},\ \{a_1,a_3\},\cdots, \{a_1,a_k\}, \\ \{a_2,a_k\},\ \{a_3,a_k\}, \cdots, \{a_{k-1},a_k\}.\tag{1}$$ Hay $2k-3$ conjuntos en esta lista, y sus sumas están en orden estrictamente creciente ya que el $a_j$ están en orden. Tenga en cuenta que desde $k\ge 3$ tenemos $2k-3 \ge k$ conjuntos en la lista para trabajar.

La idea ahora es formar un conjunto de tres elementos utilizando los conjuntos $T$ junto con el menor elemento de $B$ . Supongamos que el menor elemento de $B$ es $y=333+r.$ Luego están $r$ lagunas en $G$ a la izquierda de $y$ que se han agotado, y como $|G|=k-1$ quedan $k-1-r$ lagunas en $G$ que se encuentran a la derecha de $y.$ Así que procedemos a utilizar el menor $k-r$ de los conjuntos $T$ Cada uno de ellos, junto con $y$ y entonces, como hay al menos un conjunto más que los huecos que quedan a la derecha de $y,$ habrá al menos una $T$ tal que la suma de $T$ con $y$ no termina siendo un hueco, es decir, se encuentra en el conjunto $S$ siempre que demostremos que para cada $T$ utilizamos la suma propuesta de tres términos es menor que $1000.$

Las sumas de los $T$ están en orden creciente. Así que el mayor de ellos, siempre que utilicemos como se ha sugerido anteriormente el menor $k-r$ de ellos, es la suma para el $(k-r)$ El término de la lista $(1)$ que proporcionó $r>0$ viene de la primera línea de $(1),$ a saber, de la pareja $\{a_1,a_{k-r+1}\}$ con una suma máxima de $(332+1-k)+(332+(k-r+1)-k)=666-r-k.$ En este caso, cuando se añade a $y=333+r$ la suma es como máximo $999-k \le 1000.$ Por otro lado, si $r=0$ entonces el $(k-r)$ es decir $k$ El primer término de la lista es el primer término de la fila $(2)$ de $(1),$ así es la pareja $\{a_2,a_k\}$ con una suma máxima de $(332+2-k)+(332+k-k)=666-k,$ y luego añadir $y=333+r=333+0$ [teniendo en cuenta que este es el caso $r=0$ ] llegamos de nuevo a una suma total de a lo sumo $999-k \le 1000.$