a) Se tienen 70 números positivos distintos entre 1 y 200. Muestra que hay dos de ellos a diferencia $4$, $5$ ó $9$.
b) Se tiene la sucesión $1 = a_1 < a_2 < a_3 < \cdots$ de enteros, de modo que $a_{n+1}\leq 2n$ para cualquier $n$ entero positivo. Muestra que cualquier entero positivo es diferencia de dos términos de la sucesión.
jueves, 17 de marzo de 2011
Suscribirse a:
Comentarios de la entrada (Atom)
17 comentarios:
Creo que esta mal el de abajo, por que
$a_2\le 2*1=2$, entonces $1<a_1<a_2\le 2$ entonces pues $a_1$ no puede ser entero..
oye, pero qué pasa con el $a_{2}$? que no como $1<a_{1}<a_{2}\leq 2$ $a_{1}$ no existe en los enteros?
Inciso a) Veamos primero que buscamos un conjunto $S$ de manera que $S\subset\{1,2,...,200\}$, $|S|$ máximo y que para cualquiera $a \in S$, $a-9,a-5,a-4,a+4,a+5,a+9\notin S$ entonces, por cada $a$ que seleccionemos para meter a $S$, habrá al menos 3 números que ya no podremos meter a $S$. Para optimizar (y por ende aumentar) la cantidad de elementos dentor de $S$, es necesario hacer que los números que están en $S$ ``compartan'' a números que sacaron de los posibles números incluídos dentro de $S$, en este caso, significa que si el número $x$ no puede estar en $S$ debe ser por la mayor cantidad de ``razones'' posibles, siendo una razón, el que uno de $x-9,x-5,x-4,x+4,x+5,x+9$ esté en $S$.
Llamemos a los números ``expulsados'' de $S$ por causa de un número $a$, anti-a's. Ahora veamos que si $a,b\in S$ entonces, la mayor cantidad de anti-a's y anti-b's que puede haber son $2$, ya que si comparten a $a+4$ no pueden compartir a $a+5$ porque significa que $b=a$ ó $b=a+9$ pero ninguna debe darse, de manera similar se puede analizar para $a-4$ y $a-5$. Si comparten a $a+9$ entonces, como no pueden ser $a$, $a+4$ ni $a+5$, entonces, $b>a+9$ por lo que compartirán a lo más a $a+9$ y $a+4$ ó $a+5$. de manera similar se puede ver para $a-9$, y en caso de que no compartan a ninguno de los dos, por el argumento anterior, pueden compartir a lo más a dos, de $a-4,a-5,a+4,a+5$.
Ahora analicemos los primeros y últimos $9$ números del conjunto $\{1,2,...,200\}$ ya que en esos rangos están los números que tienen menos de $6$ anti-a's pero aún así tienen al menos $3$ anti-a's. para la $a$ correspondiente. Primero veamos que por argumentos similares a los anteriores, para cualesquiera dos números $a,b$ en esa sección, comparten a o más un anit-a que entre dentro de ese rango (un pequeño cambio en el argumento de los $a+4,a+5$) y siempre hay dos anti-a's que entran en ese rango, por lo que con el primer número que tomemos, se expulsan $2$ y con los demás se expulsan cuando menos a $1$ más, por lo que podemos tomar cuando mucho a $4$ números de ese rango, y de manera similar, podemos tomar a cuando mucho $4$ números de entre los últimos $10$. Entonces hay al menos 396 números que han sido expulsados (no necesariamente disjuntos), por lo que si buscamos que $|S|\geq 70$ entonces hay al menos un número que debió ser expulsado al menos $4$ veces. Sea este número $x$.
De aquí podemos ver que en $S$ están $4$ números de $\{x-9,x-5,x-4,x+4,x+5,x+9\}$, pero incluir al $x+4$ expulsaría a $x+9$ y a $x-5$ y entonces deberíamos incluir a los restantes, pero $x-4$ y $x-9$ se expulsan mutamente. De manera similar podemos ver que tampoco es posible para $x-4$ ni para $x+5$ por lo que como nos quedan $3$ números, no fue posible.
Inciso b)Probemos por inducción que hasta el $a_{n}$ se pueden formar todos los números naturales hasta el $n$ (ignorando el hecho de que cuando se ve la segunda propiedad para $n=2$ no funciona). Nuestro caso base, por lo mismo, será para $n=3$, en el cual vemos que $a_{3}\leq 4$ y como todos son enteros, entonces $a_{1}=2$, $a_{2}=3$ y $a_{3}=4$ y vemos que se cumple lo que queremos demostrar. Ahora supongamos que se cumple hasta $n=k$ veamos que también se cumple para $n=k+1$. Ahora, por la condición número $2$, y como $1<a_{1}$ entonces hay $k+1$ números con valores entre $2$ y $2k$ y como cada número es disjunto de otro (queriendo ver que no hay dos números a distancia $k$) y sólamente de ese (es decir, $a$ excluye a $b$ y sólamente a $b$) entonces podemos tomar a lo más, a $k$ números sin que se cumpla, sin embargo, al tomar al $k+1$ hay forzosamente $2$ números cuya distancia es $k$ por lo que hemos acabado.
Supon que los números que escogimos son:
$x_1$, $x_2$, ... , $x_70$
#ntonces consideremos las dos listas de números
$x_1$+4, $x_2$+4,...,$x_70$+4
$x_1$+9, $x_2$+9,...,$x_70$+9
Entre las 3 listas hay 210 enteros positivos que son menores o iguales a 209 por lo que por el principio de las casillas hay dos que se repiten y entonces es claro con eso vamos a entontrar los dos números con diferencia 4,5 o 9. FIN
Corregido, ese mayor era igual.
Bien Georges! Ojo con los subíndices en Latex, hay que meterlos en llaves {} para que se pongan bien.
Chuck, tu demostración del a) le faltan detalles (fácilmente remediables), pero precisamente es difícil escribir detalles si lo atacas por ese lado. Piensa en un argumento tipo casillas). Para el otro inciso hay que cambiar la demostración un poco pues usas a_1>1 (lo cual estaba mal).
Saludos
Inciso B. Tenemos que 1=a_1<=0, entonces por vacuidad es cierto
Pero para el a) precisamente usé casillas para ver que $x$ fue expulsado $4$ veces, porque los que menos expulsan son los de las orillas, así que el mínimo de expulsiones son $396$ y como seleccionamos $70$, quedan $130$ a los cuales expulsamos y por eso existe el $x$ pero en realidad no puede existir
Para el inciso b) también se puede aplicar el mismo principio, son $2k$ valores y $k+1$ números, por lo que de igual manera sucede.
a) Hmm...creo que llegué a la misma conclusión que Georges...
b) Probaremos por inducción que al restar por parejas todos los términos de $a_1 , a_2 ,..., a_k$, obtendremos todas las diferencias desde $1$ hasta $k-1$. Para $k=1,2,3,4$ es fácil comprobarlo. Ahora, supongamos que para algún $k$ se cumple. Entonces, nos queda demostrar que la diferencia de alguna pareja de términos del conjunto $a_1, a_2 ,..., a_{k+1}$ es $k$. Para esto, vemos que hay $k$ opciones para $a_{k+1}$ (que son $k+1 , k+2 ,..., 2k$, llamaremos a este conjunto $A$. Ahora, es evidente que para cada $a_i , i=1,2,...,k$, hay un elemento de $A$ a diferencia $0$ ó $k$ de $a_i$ (de lo contrario, $a_i \leq 0$ ó $a_i \geq 2k+1$) Entonces, "tacharemos" dicho elemento para cada $a_i$. Es fácil ver que no tacharemos ningún elemento más de 1 vez, ya que todos los $a_i$ son distintos, y si para un $a_j$ tachamos $a_j + k$ que está en $A$, si $a_j + k = a_l$ con $l$ entre $1$ y $k$, inclusive, $a_l$ y $a_j$ estarían a diferencia $k$ con lo que acabaríamos. Así, tacharíamos todos los elementos en $A$ dado que tiene $k$ elementos, y habrá que elegir un número tachado para $a_{k+1}$, es decir, $a_k+1$ estará a diferencia $k$ de otro término en la sucesión. Entonces, la inducción queda probada.
a) Llamemos primero a nuestros números $a_{1},a_{2},...,a_{70}$. Ahora, consideramos los números $b_{i}=a_{i}+5$ y $c_{i}=a_{i}+9$, de aquí, observamos que tenemos 210 números, es decir, hay almenos un par repetidos, ya que los valores posibles para $a_{i}$ son {1,2,3,...,200} de lo que vemos que el máximo será 209 cuando $a_{i}=200$ para algún valor de i. Ahora, como hay un par repetido, vemos que no pueden ser $a_{i's}$ repetidas, ya que son números distintos, por la misma razon, no puede haber $b_{i's}$ repetidas o $c_{i's}$ repetidas. De aquí vemos que si hubiera repetido de $a_{i}=b_{k}=a_{k}+5$, entonces habríamos escojido dos números a distancia 5; si hubieramos repetido $a_{i}=c_{k}=a_{k}+9$, habría dos números a distancia 9, y si hubiera repetidos $a_{i}+5=b_{i}=c_{k}=a_{k}+9$, habría dos a distancia a, por lo cual, queda demostrado el problema.
b) Notemos que $a_{1}=1$ y $1<a_{2}\leq2\Rightarrow a_{2}=2$, por lo que para n=1, $a_{2}-a_{1}=1$. Ahora, supongamos que hasta cierto n, se tiene que en el conjunto $\{a_{1},a_{2},a_{3},...,a_{n}\}$, están las diferencias de 1, 2, 3, ..., n-1, entonces, demostraré que en el conjunto $\{a_{1},a_{2},a_{3},...,a_{n+1}\}$, está la diferencia n, pero esto lo podemos demostrar viendo que hay n+1 números en el subconjunto de los naturales 1, 2, ..., 2n, pero por casillas, hay dos a diferencia n; entonces queda demostrado que estarán todas las diferencias.
inciso A. Digamos que elegimos los numeros (en orden creciente)a_1,...,a_70. sea b_i=5+a_i, c_i=9+a_i. Si dentro de esos 210 numeros hay dos iguales , hay dos a distancia 9-0=9,5-0=5 o 9-5=4. 209 mayor o igual a c_70 mayor o igual a c_i mayor o igual a b_i, mayor o igual a a_i mayor oigual a a_1 mayor a 1. entonces todos estan en un intervalo de 209 numeros, hay dosque se repiten y porlotanto el problema es cierto
inciso b. Consideremos los numeros a_1,...,a_{n+1}. Para todo i entre 1 y n+1 tenemos que 2n>=a_n>=a_i>=a_1=1. Entonces hay n numeros en el intervalo 1 a 2n. Partiendo el intervalo en conjuntos {i, n+i} con i entre 1 y n. Son n intervalos y n+1 numeros asi que hay dos numeros que estan en el mismo intervalo porlotanto hay dos a distancia n para cualquier n . QED
Publicar un comentario