Sea $T$ cualquier subconjunto de $\{1,2,3,...,100\}$ $69$ elementos. Demostrar que uno puede encontrar cuatro enteros distintos tales que $a+b+c=d$.

Question

Tengo una pregunta sobre combinatoria, relacionadas con el principio de casillero:

Considerar el conjunto de $S= \{1,2,3,...,100\}$. Sea $T$ cualquier subconjunto de $S$ $69$ elementos. Luego demostrar que se puede encontrar cuatro enteros distintos $a,b,c,d$ $T$ tal que $a+b+c=d$. ¿Es posible que los subconjuntos de tamaño $68$?

Answer 1

Bueno, me di cuenta que he visto este problema hace días... la solución va como esto:

Sea el número en $T$ $1\le a_1<a_2<...<a_{69}\le 100$. Claramente, $a_1\le 32$.

Ahora, consideremos las secuencias $$b_n:=a_n+a_1, 3\le n\le 69$ $ $$c_n:=a_n-a_2, 3\le n\le 69 $ $

Al parecer, $1 \le b_i,c_i\le 132$. Puesto que las dos secuencias tienen totalmente $134$ elementos (más del $132$), hay algún número en ambas secuencias, es decir, $\exists i,j\in \{3,4,\ldots,69\}$ tal que $a_i+a_1=a_j-a_2$. Entonces $a_1+a_2+a_i=a_j$, como se desee.

La segunda pregunta tiene una respuesta "falso". Contraejemplo es el conjunto de $\{33,34,\ldots,100\}$

Answer 2

Es solo una idea.

Dividir el conjunto de $T=\{a_1<a_2<...<a_{69}\}$ en dos partes. Con la primera $k$ números (set $A$) hacemos todas las sumas (set $A'$) y con el resto de los números (set $B$) hacemos diferencias positivas (set $B'$).

Decir $A= \{a_1,a_2,...a_k\}$ (por lo $a_k\leq 100-(69-k) = 31+k$) y $$A' = \{a_i+a_j|\, i\ne j; i,j\leq k\}$$

Ya tenemos: $$a_1+a_2<a_1+a_3<...<a_1+a_k<a_2+a_k<...<a_{k-1}+a_k$$

a continuación, $|A'|\geq 2k-3$ $A'\subseteq \{3,4,...61+2k\}$

Decir $B= \{a_{k+1},a_{k+2},...a_{69}\}$ (por lo $a_{k+1}\geq k$) y $$B' = \{a_i-a_j|\, i> j\geq k+1\}$$

Ya tenemos: $$a_{69}-a_{68}<a_{69}-a_{67}<...<a_{69}-a_{k+1}$$

a continuación, $|B'|\geq 68-k$ $B'\subseteq \{1,2,3,4,...99-k\}$

Ahora tenemos que elegir el apropiado $k$ tal que $|A'\cap B'|\geq 1$.

Dicen que no hay tal $k$. A continuación, $|A'\cap B'| =0$ y así: $$ |A'\cup B'| = |A'|+|B'|\geq 65+k$$

y $|A'\cup B'|\leq \max\{99-k,61+2k\}$. ...