Prove that for $n\in\mathbb{Z}^+$, a sequence of $n^3$ elements either has $n$ equal elements or a monotone subsequence with $n$ elements.

Question

Prove that $\forall n\in\mathbb{Z}^+$, a sequence with $n^3$ elements either has $n$ equal elements or a monotone subsequence with $n$ elements (strictly increasing or strictly decreasing).

I tried to apply the pigeonhole principle but had no idea how to go on. Anyone can give me a hint?

Answer 1

Without $n$ equal element, each element occurs at most $n-1$ occurrences and so there are at least $n^3/(n-1)>n^2+n+1$ distinct elements. Deleting repetitions gives a sequence of at least $n^2+n+1$ distinct elements. Now apply Erdos-Szekeres.