Sucesiones monótonas

Question

Sea $X=x_1,...,x_m$ una sucesión finita de números reales distintos dos a dos. Entonces hay sucesiones monótonas disjuntas dos a dos $X_1,...,X_l \subset X$ tales que para $i=1,...,l$, $|X_i|=\left\lceil \sqrt{m/2} \right\rceil$ y $|X_1|+...+|X_l|\geq m/2$.

Comments

No entiendo que tiene que ver que $x_i$ sean numeros reales o a que te refieres con sucesiones monotonas. $X$ bien podria ser simplemente un conjunto de $m$ elementos.
Si entiendo bien, la pregunta es: Sea $m\geq 1$ entero. Probar que
$\left\lfloor \frac{m}{\left\lceil \sqrt{m/2}\right\rceil}\right\rfloor\left\lceil \sqrt{m/2}\right\rceil \geq m/2$.

---

Una sucesión monótona es o bien, una sucesión creciente o bien, una sucesión decreciente.
Pedir que $X$ sea un conjunto de números reales distintos se puede modificar a naturales o a un subconjunto que tenga un orden total... la siguiente pregunta sería qué condiciones se le pueden quitar, pero por lo pronto lo puedes pensar como naturales.
Efectivamente, los naturales $1,...,m$ indexa a los elementos de $X$, esto es, los ordena.
¿Cómo garantizas la existencia de $l\geq \frac{m}{2\left\lceil \sqrt{m/2} \right\rceil}$ sucesiones monótonas de cardinalidad constante $\left\lceil \sqrt{m/2} \right\rceil$ dada una sucesión $X$ de $m$ elementos?

---

Aha, creo que ya entiendo. El problema es que con la notacion $\{\}$ yo entiendo un conjunto (sin un orden especifico de los elementos).
Entonces si los $x_1,\dots,x_m$ ya estan ordenados de forma creciente o decreciente, entonces la pregunta es simplemente la desigualdad que mencionaba arriba.
El problema es cuando  los $x_1,\dots,x_m$ no estan ordenados...

---

Si, es cuestión de notación, ya le he quitado las llaves para evitar ambigüedad.

Answer 1

Sea $n$ tal que $2(n+1)^2\geq m > 2n^2$. Entonces $n+1=\lceil \sqrt{m/2} \rceil$.

Ahora queremos usar el teorema de Erdoes-Szekeres (http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Szekeres_theorem):

En una sucesion con $n^2+1$ elementos siempre encontramos una subsucesion monotona de $n+1$ elementos.

Supongamos que ya escogimos subsucesiones monotonas disjuntas $X_1,X_2,\dots,X_s$ de cardinalidad $n+1$. Usando este resultado podemos escoger otra subsucesion $X_{s+1}$ si $m-s(n+1)\geq n^2+1$.

Sea $k:=\lceil \frac{m}{2(n+1)}\rceil-1$. Por lo visto arriba, lo unico que falta demostrar es que $m-k(n+1)\geq n^2+1$ o equivalentemente $m\geq k(n+1)+n^2+1$.

De la definicion de $k$ vemos que $\frac{m}{2(n+1)}>k$ o equivalentemente $m>2k(n+1)$. Entonces tenemos que

$k(n+1)+n^2+1< m/2+m/2 +1 =m+1$

y como todos son enteros, esto implica que $k(n+1)+n^2+1\leq m$. 

Comments

Hola Carlos. Muy bien, la clave es usar Erdös-Szekeres.
En el último paso muestras que al seleccionar k=n sucesiones monótonas $X_i$ ya no puedes garantizar seleccionar una más puesto que $n(n+1)+n^2+1=2n^2+n+1=z$ es un valor en $2n^2<z\leq 2(n+1)^2$ y tal vez $z > m$. Sin embargo el $k$ deseado es $n+1$. Es correcto?
En el mismo caso de que $k=n$, dices que "implica que $m=2(n+1)^2$" sin argumentar por qué de esto... :)

---

Gracias po los comentarios. Ya lo simplifique.

---

Excelente. Último par de comentarios (y no es más que por mi quisquillosidad): la variable $s$ no juega ningún papel relevante así que se puede sustituir por $k$, luego defines $k$ de cierto valor concreto para después ver que puedes tomar $k+1$ (el cuál es $l$ más pequeño que necesitamos) así que es una prueba por inducción.