Subsequências monotônicas

Toda sequência de $n^2$ números distintos possui uma subsequência monotônica com $n$ elementos.

Onde monotônica quer dizer crescente ou decrescente. Em outras palavras, dada uma sequência $a_1, a_2, a_3,\ldots a_{n^2}$, buscamos um conjunto de $I\subseteq [n^2]$ de $n$ índices tal que a subsequência $\langle a_i\rangle_{i\in I}$ é crescente ou decrescente.

Note que $n<3$ não é muito interessante.

Vamos ver o que acontece quando temos uma sequência com 9 elementos. Há 362880 possíveis ordenações, então uma análise caso a caso não parece óbvia.

O que você acha? Como resolveria o problema?