Construa uma seqüência de 16 números inteiros positivos que não tenha subseqüência crescente ou decrescente de cinco termos.
Passo 1
O enunciado pede uma sequência de
números inteiros positivos que não contenha nem uma subsequência crescente de comprimento
, nem uma subsequência decrescente de comprimento
. O conteúdo envolvido é o Teorema de Erd\H{o}s–Szekeres, que diz que qualquer sequência de
elementos tem ou uma subsequência crescente de tamanho
ou uma decrescente de tamanho
. Aqui queremos evitar ambas de tamanho
, e sabemos que
, então em
elementos é possível evitar esses dois padrões.
Passo 2
Para concretizar isso de forma construtiva, dividimos a sequência em
“blocos” de
elementos cada, de modo que cada bloco seja internamente decrescente e os blocos, tomados como números inteiros, formem uma cadeia estritamente crescente. Assim, qualquer subsequência crescente só pode pegar no máximo um elemento em cada bloco (logo, no máximo
elementos), e qualquer subsequência decrescente fica confinada a um único bloco (no máximo
elementos).
Passo 3
Escolhendo blocos de
elementos conforme dito, obtemos a sequência explícita
Passo 4
– Qualquer subsequência crescente não pode selecionar dois elementos de um mesmo bloco porque dentro dele os números descem; assim ela pega no máximo um elemento de cada um dos
blocos, ou seja, tem comprimento
.
– Qualquer subsequência decrescente não pode atravessar blocos, pois os blocos são disjuntos e em blocos posteriores todos os valores são maiores do que em blocos anteriores; logo uma subsequência decrescente ocorre inteiramente dentro de um único bloco, tendo comprimento .
– Qualquer subsequência decrescente não pode atravessar blocos, pois os blocos são disjuntos e em blocos posteriores todos os valores são maiores do que em blocos anteriores; logo uma subsequência decrescente ocorre inteiramente dentro de um único bloco, tendo comprimento
Resposta
A sequência
não possui subsequência nem crescente nem decrescente de comprimento
.