Mostre que toda sequência de
inteiros diferentes possui uma subsequência crescente com
termos ou uma subsequência decrescente com
termos.
Passo 1
Beleza, vamos lá! O enunciado pede para mostrar que qualquer sequência de $ n^{2} + 1 $ números inteiros diferentes tem ou uma subsequência crescente com $ n+1 $ termos ou uma decrescente com $ n+1 $ termos. Para resolver isso, vamos usar um conceito chamado princípio da Casa dos Pombos (ou princípio de Dirichlet) e um pouquinho de lógica sobre sequências crescentes e decrescentes.
Passo 2
Primeiro, vamos entender o que é uma subsequência crescente e uma decrescente. Uma subsequência crescente é uma parte da sequência original onde cada número é maior que o anterior. Por exemplo, em $ 3, 1, 4, 2, 5 $, a subsequência $ 1, 2, 5 $ é crescente. Já uma subsequência decrescente tem cada número menor que o anterior, como $ 4, 2 $.
Passo 3
Agora, vamos associar a cada número da nossa sequência original dois valores:
- Comprimento da maior subsequência crescente que termina nesse número.
- Comprimento da maior subsequência decrescente que termina nesse número.
Vamos chamar esses valores de $ C_i $ e $ D_i $ para o $ i $-ésimo número da sequência.
Passo 4
A ideia é que, para cada número na sequência, ou a subsequência crescente ou a decrescente que termina nele atinge um certo tamanho. Se conseguirmos mostrar que em uma sequência de $ n^{2}+1 $ números, pelo menos um desses valores $ C_i $ ou $ D_i $ chega a $ n+1 $, teremos provado o que precisa.
Passo 5
Para isso, observamos que existem $ n $ possíveis valores para $ C_i $ (de 1 a $ n $) e $ n $ possíveis para $ D_i $. Então, cada número da sequência associa-se a um par $ (C_i, D_i) $. Com $ n^{2} $ combinações possíveis e $ n^{2}+1 $ números, pelo princípio da Casa dos Pombos, pelo menos dois números devem ter o mesmo par $ (C_i, D_i) $.
Passo 6
Se isso acontece, significa que entre eles existe uma subsequência tanto crescente quanto decrescente que pode ser estendida. Isso leva à conclusão de que deveríamos ter uma subsequência com $ n+1 $ termos em um dos dois casos: crescente ou decrescente.
Passo 7
Portanto, se a nossa sequência tem $ n^{2}+1 $ números diferentes, obrigatoriamente existe ou uma subsequência crescente com $ n+1 $ termos ou uma decrescente com $ n+1 $ termos, conforme o que foi pedido.
Resposta
Dessa forma, mostramos que toda sequência de $ n^{2} + 1 $ inteiros diferentes possui uma subsequência crescente com $ n+1 $ termos ou uma subsequência decrescente com $ n+1 $ termos.