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
pessoas com alturas todas distintas, sempre existe uma subsequência de
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
nem subsequência decrescente de tamanho
. Para cada pessoa na posição
da fila (com altura
), defina:
Por hipótese, temos
e
para todo
.
Passo 3
Os pares
pertencem ao conjunto
, que tem exatamente
elementos. Como há
pessoas, pelo princípio da casa dos pombos existem índices
tais que
Por outro lado, as alturas são todas distintas, então ou
ou
:
- Se
, então qualquer subsequência crescente de comprimento iniciada em pode ser precedida por , dando uma subsequência crescente de comprimento iniciada em . Logo , o que contradiz . - Se
, então análogo raciocínio em subsequências decrescentes mostra , contradizendo .
Passo 4
Essa contradição mostra que nossa hipótese inicial era falsa. Portanto, necessariamente existe uma subsequência de
pessoas cujas alturas estão em ordem estritamente crescente ou estritamente decrescente.
Resposta
Em qualquer fila de
pessoas de alturas distintas há sempre uma subsequência de
pessoas em ordem de altura crescente ou decrescente.