S06 O teorema de Erdős e Szekeres
Seja \(x\) uma sequência $x_0,x_1,\dots,x_{N-1}$ de inteiros. Vamos dizer neste exercício que $x$ é crescente se $x_0\leq x_1\leq\dots\leq x_{N-1}$ e que $x$ é decrescente se $x_0>x_1>\dots>x_{N-1}$. Como de usual, uma subsequência de $x$ é uma sequência da forma $x_{i_0},x_{i_1},\dots,x_{i_{k-1}}$, onde $0\leq i_0<i_1<\dots<i_{k-1}<N$.
Um teorema bem conhecido de Erdős e Szekeres é o seguinte.
Teorema. Sejam $a$ e $b$ inteiros não-negativos e seja $N=ab+1$. Toda sequência com $N$ elementos ou tem uma subsequência crescente com $a+1$ elementos ou tem uma subsequência decrescente com $b+1$ elementos.
Sua tarefa. Neste exercício, você deve deduzir o teorema de Erdős e Szekeres acima do teorema de Hammersley, provado em sala na aula de 29/5/2025.
Observações
- A prova que vimos do teorema de Hammersley é algorítmica. No Exercício E07 (em preparação), você irá implementar o algoritmo de Hammersley.
- Várias demonstrações do teorema de Erdős e Szekeres são conhecidas. Neste exercício, você deve deduzir o teorema de Erdős e Szekeres do teorema de Hammersley.