Teorema de la Subsucesión Monótona

Teoría

El Teorema de la Subsucesión Monótona, conocido formalmente como el Teorema de Erdős-Szekeres, es un resultado fundamental en combinatoria y teoría de Ramsey. Dice que cualquier sucesión de números reales distintos que sea lo suficientemente larga debe tener una subsucesión monótona "larga". Específicamente, garantiza que en un conjunto de datos lo suficientemente grande no puedes evitar el orden por completo; si intentas armar una sucesión que no tenga una tendencia creciente larga, la matemática te obliga a crear una tendencia decreciente larga, y al revés.

Este teorema es una aplicación clásica del Principio de las Casillas y sirve como un ejemplo principal de esa idea de la teoría de Ramsey que dice que el desorden total es imposible en estructuras suficientemente grandes. En las olimpiadas de matemáticas, este teorema se usa seguido en problemas sobre el orden de conjuntos finitos, permutaciones y geometría discreta (como probar que existen polígonos convexos dentro de conjuntos grandes de puntos). La intuición es que para evitar que una subsucesión creciente se haga larga, los términos tienen que ir bajando, pero al hacer eso una y otra vez, terminas armando una subsucesión decreciente.

Fórmulas Clave

El Teorema de Erdős-Szekeres Para cualquier par de enteros $r, s \ge 1$, cualquier sucesión de números reales distintos con una longitud de al menos $(r-1)(s-1) + 1$ contiene ya sea:

1. Una subsucesión creciente de longitud $r$, o
2. Una subsucesión decreciente de longitud $s$.

El Caso Simétrico Una variación común en las olimpiadas es poner $r = s = n+1$. El teorema dice que cualquier sucesión de $n^2 + 1$ números reales distintos contiene una subsucesión monótona (ya sea creciente o decreciente) de longitud $n+1$.

Formalmente, toma $A = (a_1, a_2, \dots, a_N)$ como una sucesión de números reales. $$N \ge (r-1)(s-1) + 1 \implies \exists i_1 < i_2 < \dots < i_k \text{ tal que }$$ $$a_{i_1} < a_{i_2} < \dots < a_{i_k} \quad \text{con } k=r$$ $$\text{O}$$ $$a_{i_1} > a_{i_2} > \dots > a_{i_k} \quad \text{con } k=s$$

Demostración

Aquí tienes la demostración estándar usando el Principio de las Casillas, que se le atribuye a Seidenberg (1959).

Teorema: Una sucesión de $(r-1)(s-1)+1$ números reales distintos contiene una subsucesión creciente de longitud $r$ o una subsucesión decreciente de longitud $s$.

Demostración: Imagina que la sucesión es $a_1, a_2, \dots, a_N$, donde $N = (r-1)(s-1) + 1$. Para cada término $a_i$ de la sucesión (donde $1 \le i \le N$), asígnale un par de enteros $(u_i, v_i)$ definidos de esta forma:

• $u_i$: la longitud de la subsucesión creciente más larga que termina en $a_i$.
• $v_i$: la longitud de la subsucesión decreciente más larga que termina en $a_i$.

Usa una contradicción. Supón que el teorema es falso. Esto implica que:

1. La subsucesión creciente más larga tiene una longitud de a lo mucho $r-1$. Por lo tanto, $1 \le u_i \le r-1$ para toda $i$.
2. La subsucesión decreciente más larga tiene una longitud de a lo mucho $s-1$. Por lo tanto, $1 \le v_i \le s-1$ para toda $i$.

Con esta suposición, los valores posibles para el par $(u_i, v_i)$ están limitados a la cuadrícula $[1, r-1] \times [1, s-1]$. El número total de pares distintos posibles es: $$(r-1) \times (s-1)$$

Sin embargo, la longitud de la sucesión es $N = (r-1)(s-1) + 1$. Por el Principio de las Casillas, como hay más términos en la sucesión (palomas) que pares distintos posibles (casillas), tienen que existir dos índices distintos $i$ y $j$ con $i < j$ tales que: $$(u_i, v_i) = (u_j, v_j)$$

Analiza la relación entre $a_i$ y $a_j$. Como los números son distintos, o bien $a_i < a_j$ o bien $a_i > a_j$.

Caso 1: $a_i < a_j$ Como $a_i < a_j$ e $i < j$, puedes extender cualquier subsucesión creciente que termine en $a_i$ agregando $a_j$ al final. Entonces, la subsucesión creciente más larga que termina en $a_j$ tiene que ser al menos uno más grande que la subsucesión creciente más larga que termina en $a_i$. $$u_j \ge u_i + 1$$ Esto contradice la suposición de que $u_i = u_j$.

Caso 2: $a_i > a_j$ Como $a_i > a_j$ e $i < j$, puedes extender cualquier subsucesión decreciente que termine en $a_i$ agregando $a_j$ al final. Entonces, la subsucesión decreciente más larga que termina en $a_j$ tiene que ser al menos uno más grande que la subsucesión decreciente más larga que termina en $a_i$. $$v_j \ge v_i + 1$$ Esto contradice la suposición de que $v_i = v_j$.

En ambos casos llegas a una contradicción. Por lo tanto, la suposición de que no existen tales subsucesiones tiene que ser falsa. La sucesión debe contener una subsucesión creciente de longitud $r$ o una subsucesión decreciente de longitud $s$. $\square$