Questão 5 Mostrar que toda sequência com n^{2}+1 números reais contém ou uma subsequência crescente com n+1 termos ou uma subsequência decrescente com n+1 termos.
Passo 1
O enunciado diz que temos uma sequência de n^{2}+1 números reais e queremos mostrar que nela sempre aparece ou uma subsequência estritamente crescente com n+1 termos ou uma subsequência estritamente decrescente com n+1 termos. O conteúdo principal é o uso do princípio da casa dos pombos aplicado às “larguras” de subsequências crescentes.
com a convenção de que c(i)=1 se não existir nenhum k<i com x_k<x_i. Por definição, c(i) é o comprimento da maior subsequência crescente que termina em x_i.
Passo 3
Se existir algum índice i tal que c(i)\ge n+1, então acabamos de encontrar uma subsequência crescente de comprimento n+1 e estamos feitos. Caso contrário, concluímos que
c(i)\le n \quad\text{para todo }i.
Passo 4
Agora agrupamos os índices em n classes de acordo com o valor de c(i). Definimos
A_j = \{\,i \mid c(i)=j\}, \quad j=1,2,\dots,n.
Como há n^{2}+1 índices no total e apenas n classes A_j, pelo princípio da casa dos pombos existe algum j tal que
Mostramos que os elementos cujos índices estão em A_j formam uma subsequência estritamente decrescente de tamanho \ge n+1. De fato, se i<k e ambos estão em A_j, então c(i)=c(k)=j. Se tivéssemos x_i<x_k, então a maior subsequência crescente até x_k teria comprimento pelo menos j+1, contra c(k)=j. Logo x_i>x_k. Assim, ordenando os n+1 índices de A_j na ordem natural, obtemos uma subsequência decrescente de comprimento n+1.
Resposta
Com isso, mostramos que em qualquer sequência de n^{2}+1 reais existe ou uma subsequência crescente de n+1 termos ou uma subsequência decrescente de n+1 termos.