*43. Uma demonstração do Teorema 3 baseada na generalização do princípio da casa dos pombos é apresentada neste exercício. A notação usada é a mesma da demonstração no texto.
a) Suponha que i_{k} \leq n para k=1,2, \ldots, n^{2}+1. Use a generalização do princípio da casa dos pombos para mostrar que há n+1 termos a_{k_{1}}, a_{k_{2}}, \cdots, a_{k_{n+1}} com i_{k_{1}}=i_{k_{2}}=\cdots=i_{k_{n+1}}, em que 1 \leq k_{1}<k_{2}<\cdots<k_{n+1}.
b) Mostre que a_{k,}>a_{k_{j+1}} para j=1,2, \ldots, n. [Dica: Suponha que a_{k_{j}}<a_{k_{j+1}}, e mostre que isto implica que i_{k_{j}}>i_{k_{j+1}}, o que é uma contradição.]
c) Use os itens (a) e (b) para mostrar que se não houver subseqüência crescente de extensão n+1, então deverá haver uma subseqüência decrescente com a mesma extensão.

Passo 1

O enunciado propõe uma demonstração do Teorema 3 usando a generalização do princípio da casa dos pombos. Trabalhamos com uma sequência de comprimento n^{2}+1 e, para cada termo a_{k}, definimos i_{k} como a extensão máxima de uma subsequência crescente que comece em a_{k}. Precisamos mostrar:
a) Se todos os i_{k} satisfazem i_{k}\le n, então existem n+1 termos com o mesmo valor de i_{k}.
b) Esses n+1 termos formam uma subsequência estritamente decrescente.
c) Concluímos que, se não há subsequência crescente de extensão n+1, então existe uma subsequência decrescente de extensão n+1.

Passo 2

Para (a), aplicamos o princípio da casa dos pombos generalizado colocando cada termo a_{k} na “casa” numerada por i_{k}. Como i_{k}\in\{1,2,\dots,n\} são n casas e temos n^{2}+1 termos (pombos), a generalização garante que alguma casa contém pelo menos
\big\lceil\tfrac{n^{2}+1}{n}\big\rceil = n+1
pombos. Logo existem índices 1\le k_{1}<k_{2}<\cdots<k_{n+1} tais que
i_{k_{1}}=i_{k_{2}}=\cdots=i_{k_{n+1}}\,.

Passo 3

Para (b), mostremos que esses termos satisfazem
a_{k_{1}}>a_{k_{2}}>\cdots>a_{k_{n+1}}\,.
Suponha, por contradição, que para algum j tivéssemos a_{k_{j}}<a_{k_{j+1}}. Como i_{k_{j+1}} é o tamanho máximo de uma subsequência crescente iniciando em a_{k_{j+1}}, podemos concatenar a_{k_{j}} antes dessa subsequência e obter uma subsequência crescente de comprimento i_{k_{j+1}}+1 começando em a_{k_{j}}. Isso daria
i_{k_{j}}>i_{k_{j+1}},
o que contraria i_{k_{j}}=i_{k_{j+1}}. Portanto necessariamente a_{k_{j}}>a_{k_{j+1}} para todo j.

Passo 4

Para (c), se não houver subsequência crescente de extensão n+1, então de fato i_{k}\le n para todo k. Pelos itens (a) e (b) encontramos n+1 termos com o mesmo i_{k} que formam uma subsequência estritamente decrescente. Concluímos que a falta de uma sequência crescente longa implica a existência de uma sequência decrescente igualmente longa.

Resposta

Se não há subsequência crescente de extensão n+1, então existe uma subsequência decrescente de extensão n+1.

Exercícios relacionados