Mostre que se houver 101 pessoas de alturas diferentes paradas em fila, é possível encontrar 11 pessoas na ordem que estão paradas em uma seqüência de alturas crescente ou decrescente.

Passo 1

O enunciado pede para mostrar que, em qualquer sequência de 101 pessoas com alturas todas distintas, sempre existe uma subsequência de 11 pessoas cujas alturas estão em ordem estritamente crescente ou estritamente decrescente. O conteúdo envolvido é o Teorema de Erd\H{o}s–Szekeres, que usa o princípio da casa dos pombos em pares ordenados.

Passo 2

Suponha, por absurdo, que não exista nem subsequência crescente de tamanho 11 nem subsequência decrescente de tamanho 11. Para cada pessoa na posição i da fila (com altura a_i), defina:
L_i = \text{comprimento da maior subsequência crescente que se inicia em }i,ê
D_i = \text{comprimento da maior subsequência decrescente que se inicia em }i.ê
Por hipótese, temos L_i \le 10 e D_i \le 10 para todo i.

Passo 3

Os pares (L_i,D_i) pertencem ao conjunto \{1,2,\dots,10\}\times\{1,2,\dots,10\}, que tem exatamente 10\times10=100 elementos. Como há 101 pessoas, pelo princípio da casa dos pombos existem índices i<j tais que
(L_i,D_i) \;=\;(L_j,D_j).
Por outro lado, as alturas são todas distintas, então ou a_i<a_j ou a_i>a_j:
  • Se a_i<a_j, então qualquer subsequência crescente de comprimento L_j iniciada em j pode ser precedida por a_i, dando uma subsequência crescente de comprimento L_j+1 iniciada em i. Logo L_i\ge L_j+1, o que contradiz L_i=L_j.
  • Se a_i>a_j, então análogo raciocínio em subsequências decrescentes mostra D_i\ge D_j+1, contradizendo D_i=D_j.

Passo 4

Essa contradição mostra que nossa hipótese inicial era falsa. Portanto, necessariamente existe uma subsequência de 11 pessoas cujas alturas estão em ordem estritamente crescente ou estritamente decrescente.

Resposta

Em qualquer fila de 101 pessoas de alturas distintas há sempre uma subsequência de 11 pessoas em ordem de altura crescente ou decrescente.

Exercícios relacionados