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.

Passo 2

Para cada posição i da sequência, definimos
c(i) = 1 + \max\bigl\{\,c(k)\mid k<i \text{ e } x_k < x_i\bigr\},
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
\bigl|A_j\bigr|\;\ge\;\Bigl\lceil\frac{n^{2}+1}{n}\Bigr\rceil\;=\;n+1.

Passo 5

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.

Exercícios relacionados