jueves, 19 de mayo de 2011

Problema del día: 19 de Mayo (Centros)

S es un subconjunto de {1,2,3,......,1000} tal que si m y n son elementos distintos de S, entonces m+n  no pertenece a S.
¿Cual el el numero mas grande de elementos que puede tener S?

3 comentarios:

Juan dijo...

La respuesta es $501$ con $S=\{500, 501, 502, ..., 998, 999, 1000\}$.
Llamemos $A$ al conjunto de los elementos de S que son $\ge 500$, y $B=S-A$.
Si $500 \in S$, entonces $|A| \le 501 - |B| \le 501$ (pues de los 501 elementos en $A$ posibles, $|B|$ son cancelados por $B+500$). Acabamos en este caso.
Si $500$ no está en $S$, llamémosle $m$ al mínimo elemento de $A$. Aquí, hay al menos $|B| - m + 501$ elementos de $B$ tal que $x+m \le 1000$, pues para que $x+m$ se pase de 1000, $x \ge 1001-m$, así, $1001-m \ge 499$ y hay a lo más $501-m$ elementos que cumplen ésto, y el resto, $|B| - m + 501$, sí cumplen.
Ahora, en $|A|$, hay a lo más $(1000 - m + 1 )- (|B| - m + 501) = 500 - |B|$ elementos, y así $|S| = |A| + |B| \le 500$, y acabamos.

Adán dijo...

Sea $A$ el mayor elemento en $S$.

Ahora, veamos que si $a\in S$ entonces no es posible que $A-a\in S$. Ahora, esto nos dice que nuestro conjunto tiene a lo más piso de $\frac{A+2}{2}$ elementos.

Ahora, como $A\leq 1000$ tomamos $A=1000$ y tomamos a

$S=\{500, 501,\ldots, 1000\}.$

Vemos que ese subconjunto $S$ cumple las condiciones del problema y maximiza el número de elementos que puede tener $S$, por lo que $501$ es el máximo número de elementos que puede tener $S$.

Enrique dijo...

Decimos que una pareja de números $(a,b)$ ``cancela'' a un número si hace que éste no pueda estar en $S$. Entonces, $(a,b)$ cancela a $a+b$ y a $a-b$ (suponiendo que $a\geq b$ y que $a\neq 2b$),.ya que $(a-b)+b=a$. Entonces, si tomamos los elementos $a_{1},a_{2},...,a_{n}$ de $S$, con $a_{1}\geq a_{2}\geq ...\geq a_{n} $, entonces las parejas $(a_{1},a_{2}), (a_{1},a_{3}),..., (a_{1},a_{n})$ cancelan a $a_{1}-a_{2},a_{1}-a_{3},...,a_{1}-a_{n}$, que son $n-1$ diferencias diferentes. Ahora, notemos que si $a=2b$, entonces $(a,b)$ no cancela a $a-b=b$. Como $a_{1}=2a_{k}$ para a lo más un $k$ entre $1$ y $n$, hay al menos $n-2$ números cancelados. Entonces, si $1000-n=n-2\Rightarrow n=501$, y es fácil ver que $S=\{500,501,...,1000\}$ cumple la condición. $\blacksquare$

Publicar un comentario