*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
para
. Use a generalização do princípio da casa dos pombos para mostrar que há
termos
com
, em que
.
b) Mostre que
para
. [Dica: Suponha que
, e mostre que isto implica que
, 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
, então deverá haver uma subseqüência decrescente com a mesma extensão.
a) Suponha que
b) Mostre que
c) Use os itens (a) e (b) para mostrar que se não houver subseqüência crescente de 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
e, para cada termo
, definimos
como a extensão máxima de uma subsequência crescente que comece em
. Precisamos mostrar:
a) Se todos os satisfazem
, então existem
termos com o mesmo valor de
.
b) Esses termos formam uma subsequência estritamente decrescente.
c) Concluímos que, se não há subsequência crescente de extensão , então existe uma subsequência decrescente de extensão
.
a) Se todos os
b) Esses
c) Concluímos que, se não há subsequência crescente de extensão
Passo 2
Para (a), aplicamos o princípio da casa dos pombos generalizado colocando cada termo
na “casa” numerada por
. Como
são
casas e temos
termos (pombos), a generalização garante que alguma casa contém pelo menos
pombos. Logo existem índices
tais que
Passo 3
Para (b), mostremos que esses termos satisfazem
Suponha, por contradição, que para algum
tivéssemos
. Como
é o tamanho máximo de uma subsequência crescente iniciando em
, podemos concatenar
antes dessa subsequência e obter uma subsequência crescente de comprimento
começando em
. Isso daria
o que contraria
. Portanto necessariamente
para todo
.
Passo 4
Para (c), se não houver subsequência crescente de extensão
, então de fato
para todo
. Pelos itens (a) e (b) encontramos
termos com o mesmo
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
, então existe uma subsequência decrescente de extensão
.