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 16 números inteiros positivos que não contenha nem uma subsequência crescente de comprimento 5, nem uma subsequência decrescente de comprimento 5. O conteúdo envolvido é o Teorema de Erd\H{o}s–Szekeres, que diz que qualquer sequência de (m-1)(n-1)+1 elementos tem ou uma subsequência crescente de tamanho m ou uma decrescente de tamanho n. Aqui queremos evitar ambas de tamanho 5, e sabemos que (5-1)(5-1)+1=17, então em 16 elementos é possível evitar esses dois padrões.

Passo 2

Para concretizar isso de forma construtiva, dividimos a sequência em 4 “blocos” de 4 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 4 elementos), e qualquer subsequência decrescente fica confinada a um único bloco (no máximo 4 elementos).

Passo 3

Escolhendo blocos de 4 elementos conforme dito, obtemos a sequência explícita
(4,3,2,1,\;8,7,6,5,\;12,11,10,9,\;16,15,14,13).

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 4 blocos, ou seja, tem comprimento \le4.
– 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 \le4.

Resposta

A sequência
(4,3,2,1,\;8,7,6,5,\;12,11,10,9,\;16,15,14,13)
não possui subsequência nem crescente nem decrescente de comprimento 5.

Exercícios relacionados