Mostre 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.

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:
  1. Comprimento da maior subsequência crescente que termina nesse número.
  2. 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.

Exercícios relacionados