T06 Erdős--Szekeres
Seja \(x_1,x_2,\dots,x_N\) uma sequência de números reais. Dizemos que uma subsequência $x_{i_1},x_{i_2},\dots,x_{i_r}$ ($i_1<i_2<\dots<i_r$) da sequência original $x_i$ ($1\leq i\leq N$) é estritamente crescente se $x_{i_1}<x_{i_2}<\dots<x_{i_r}$. Dizemos que esta subsequência é decrescente se $x_{i_1}\geq x_{i_2}\geq \dots\geq x_{i_r}$.
(1) Prove que a sequência dos $x_i$ ($1\leq i\leq N$) acima com $N=ab+1$, onde $a$ e $b$ são inteiros não-negativos, necessariamente ou contém uma subsequência estritamente crescente com $a+1$ elementos ou contém uma subsequência decrescente com $b+1$ elementos.
(2) Prove que, para todo $a$ e $b$ inteiros não-negativos, a afirmação em (1) deixa de valer se $N=ab$.
(3) Podemos definir subsequências crescentes e estritamente decrescentes de forma análoga. Formule uma afirmação como em (1) envolvendo subsequências crescentes e estritamente decrescentes.
(4) Repita (2) com sua afirmação em (3).