miércoles, 9 de febrero de 2011

Problema del día: Sucesiones superaditivas, corregido

Una sucesión no decreciente de números enteros no negativos $\{s_n\}$ se llama superaditiva si $s_{i+j}\geq s_i+s_j$ para cualesquiera enteros no negativos $i$ y $j$. Supongamos que $\{s_n\}$ y $\{t_n\}$ son sucesiones superaditivas. Consideremos la sucesión $\{u_n\}$ no decreciente tal que cada entero aparece tantas veces en ella como en $\{s_n\}$ y $\{t_n\}$ combinadas (por ejemplo, si hay cinco $3$ en las $s_n$ y cuatro en las $t_n$ entonces en las $u_n$ hay nueve).

Muestra que $\{u_n\}$ también es superaditiva.

9 comentarios:

jorge garza vargas dijo...

Hola Leo!.. disculpa, no me quedó muy claro cómo se construye {U_n}. Lo que entendí con lo escrito al principio es que si "m" es un entero y S la cantidad de veces que aparece m en {s_n} y T la cantidad de veces que aparece m en {t_n} entonces m aparece S+T veces en {U_n}, pero eso no concuerda con el ejemplo. Lo podrías explicar de otra forma porfa?

Flavio dijo...

me imagino que en {U_n} los elementos se ordenan de menor a mayor o no?

Flavio dijo...

a si no habia leido lo de no decreciente, lo siento

Jorge 'Chuck' dijo...

$\{s_{n}\}$ y $\{t_{n}\}$ son sucesiones de enteros?

Leo dijo...

Jorge: Es lo que entendiste, pero en el ejemplo tengo un error de dedo. En realidad, deberían aparecer 9 veces el 3.

Chuck: Los números de estas sucesiones son enteros no negativos!!

Ahorita corrijo estas dos cosas

jorge garza vargas dijo...
Este comentario ha sido eliminado por el autor.
jorge garza vargas dijo...

Solución. Parte 1.
Lema 1: si s_a y t_b pertenecen a {S_n} y {t_b} respectivamente entonces máx{s_a,t_b}>u_(a+b+1).
Demostración de lema 1. Lo demostraremos por contradicción, supongamos que u_(a+b+1)> máx{s_a,t_b}, por la manera en que {U_n} está construida tenemos que s_i<u_a+b+1 para i=0,1,2…,a y que entonces s_i (para i=1,2,…,a) es un término de {U_n}con subíndice menor a (a+b+1) ya que {U_n} es no decreciente, análogamente t_i<u_(a+b+1) para i=0,1,2…b entonces t_i es un elemento de {U_n} con subíndice menor a (a+b+1), entonces la sucesión {U_n}tiene al menos (a+1)+(b+1)=a+b+2 términos menores a u_(a+b+1) lo cual es una contradicción ya que {U_n}es no decreciente por lo que tiene exactamente a+b+1 términos menores o iguales a u_(a+b+1).

jorge garza vargas dijo...

Parte 2.
Supongamos que entre los términos de {U_n} mayores a u_i y menores o iguales a u_(i+j) hay “a” términos que “fueron tomados” de {S_n} al construir {U_n} (sean s_(m+1), s_(m+2)…s_(m+a) dichos términos) y “b” términos que fueron tomados de {T_n} al construir {U_n} (sean t_(n+1), t_(n+2)…(t_n+b) dichos términos), entonces por definición a+b=j. Sin pérdida de generalidad podemos suponer que que u_i está en {S_n}, así que u_i=s_m, entonces como {S_n} es superaditiva se tiene que u_(i+j)>s_(m+a)>s_m + s_a=u_i + s_a, análogamente como {T_n} es superadictiva tenemos que u_(i+j)>t_(n+b)>t_(n+1) + t_(b-1)>u_i + t_(b-1). Sea k=máx{s_a,t_(b-1)} entonces por el lema 1 tenemos que k>u_(a+b)=u_j, entonces como u_(i+j)> u_i + s_a, y u_(i+j)> u_i + t_(b-1) se tiene que u_(i+j)>u_i + k>u_i + u_j, por lo tanto {U_n} es superaditiva.
[en la notación usada (tanto en la parte 1 como en la parte 2) : m>n significa m mayor o igual que n, y m<n significa m menor estricto a n].

Jorge 'Chuck' dijo...

Supongamos que para la creación de $\{u_{n}\}$ utilizamos como base a $\{t_{n}\}$ y le fuimos metiendo entre un número y otro los valores de la sucesión de $\{s_{n}\}$ de manera que queden de manera no decreciente. Veamos lo que pasa con $t_{i}+t_{j}\leq t_{i+j}$ cuando vemos dónde quedaron en $\{u_{n}\}$.
Primero, si se pusieron $y$ valores entre $t_{i}$ y $t_{j}$ entonces en $\{u_{n}\}$ serán $u_{i+x+y}$ y $u_{j+x}$ respectivamente, para alguna $x$ entera no negativa. Entonces sabemos que $u_{i+x+y}+u_{j+x}\leq u_{i+j+x+y+z}$ siendo $z$ la cantidad de valores que fueron insertados entre $t_{i}$ y $t_{i+j}$, por lo que si $z\leq x$ como es una sucesión no decreciente, se sigue cumpliendo ya que los valores siguientes a $u_{i+j+x+y+z}$ son mayores o iguales a éste, y como eso es lo que buscamos que se siga cumpliendo, este caso está cubierto.
Primero probemos un lema que dice que si en los primeros $b$ números, la sucesión superaditiva crece en $c$ entonces en cualquier conjunto $b$ valores continuos de la sucesión, la sucesión crece en al menos $c$ (me refiero al valor de la sucesión en ese punto). Pero en realidad es fácil de ver puesto que por la definicion de sucesión superaditiva nos lo dice para $s_{b}+s_{i}\leq s_{i+b}$ de donde sacamos que $s_{b}\leq s_{i+b}-s_{i}$ y está demostrado.
Usando este lema podemos ver que si antes de $t_{j}$ hubo x valores de $\{s_{n}\}$ entonces para el $x+1$ ya incrementó en mas de $t_{j}$ por lo que entre $t_{i}$ y $t_{i+j}$ puede haber a lo más $x$ valores de $\{s_{n}\}$ porque para el siguiente, se pasaría, por lo tanto todos los casos posibles en los que los dos números que se suman provienen de una misma sucesión están cubiertos ya que $z$ siempre es menor o igual que $x$.
Supongamos que tomamos un valor de $\{s_{n}\}$ y otro de $\{t_{n}\}$ y queremos ver si se cumple la regla de las superaditivas con ellos. Sean $s_{i}$ y $t_{a}$ los números de los que hablamos, y supongamos que en $\{u_{n}\}$ son $u_{i+b}$ y $u_{a+j}$ para algún $b$ y $j$ enteros no negativos. Supongamos sin pérdida de generalidad que $u_{a+b+i+j}$ provenía de $\{t_{n}\}$. Ahora, veamos que $t_{b+1}\geq s_{i}$ y que por lo mismo $t_{a+b+1}\geq t_{a}+t_{b+1}\geq t_{a}+s_{i}$, $t_{a+b}$ es en $\{u_{n}\}$ cuando mucho, por el lema que demostramos, $u_{a+b+i+j-1}$ ya que antes de $t_{a}$ hay $j$ de $\{s_{n}\}$ y antes de $t_{b}$ hay menos de $i$ de $\{s_{n}\}$ por lo que si aumentamos a un valor el subíndice, de ser $t_{b}$ tomamos a $t_{b+1}$ (que como $\{t_{n}\}$ es superaditiva, debe cumplir sus propiedades, y es $t_{a+b+1}$) entonces como el valor siguiente en $\{u_{n}\}$ que proviene de $\{t_{n}\}$ está entre el que es $t_{a+b}$, que es menor o igual a $u_{a+b+i+j-1}$ y $u_{a+b+i+j}$ entonces es cuando mucho el segundo y entonces $u_{a+b+i+j}$ es mayor o igual $t_{a+b+1}$ que como habíamos visto, es mayor o igual que $t_{a}+s_{i}$ y ha quedado demostrado este otro caso. Por lo tanto, $\{u_{n}\}$ también es superaditiva.

Publicar un comentario